【資料結構】判斷給定的二叉樹是否為BST樹（二叉搜尋樹）

分析：

對于每個結點，需要檢查其左子樹中的最大值是否小于目前結點的值，且右子樹中的最小值是否大于目前結點的值

而我們知道對于一棵二叉樹搜尋樹來說，其每一棵子樹也都是二叉搜尋樹，且其最小值為最左邊的結點，最大值為最右邊的結點。

是以反過來講，就是如果一棵普通二叉樹的任意一棵左子樹中的最大值（左子樹的最右邊結點）大于等于目前根結點或者任意一棵右子樹的最小值（右子樹的最左邊結點）小于目前根結點，那麼這棵樹就不是二叉搜尋樹。

此算法時間複雜度為O（ n 2 n^2 n2），空間複雜度為O（ n n n）

Java版本實作

//擷取左子樹最右邊結點
    int getBRightOfLeftTree(BinaryTreeNode<T> root){
    	BinaryTreeNode<T> left = root.getLeft();
    	if(left == null) {
    		System.out.println("最大值：" + ((int)root.getData() - 1));
    		return (int)root.getData() - 1;
    	}
    		
    	while(left.getRight() != null) {
    		left = left.getRight();
    	}
    	System.out.println("最大值" + (int) left.getData());
    	return (int) left.getData();
    }
    
    //擷取右子樹的最左邊結點
    int getBLeftOfRightTree(BinaryTreeNode<T> root) {
    	BinaryTreeNode<T> right = root.getRight();
    	if(right == null) {
    		System.out.println("最小值：" + ((int)root.getData()));
    		return (int)root.getData();
    	}
    		
    	while(right.getLeft() != null) {
    		right = right.getLeft();
    	}
    	System.out.println("最小值" + (int) right.getData());
    	return (int) right.getData();
    }
   
    //判斷給定的二叉樹是否為BST樹
    boolean isBST(BinaryTreeNode<T> root) {
    	if(root == null)
    		return true;
    	//左子樹的最右邊值大于根結點傳回false
    	if(root.getLeft() != null && getBRightOfLeftTree(root) >= (Integer)root.getData())
			return false;
    	//右子樹的最左邊結點小于根結點傳回false
		if(root.getRight() != null && getBLeftOfRightTree(root) < (Integer)root.getData())
			return false;
		//遞歸判斷左子樹和右子樹，若其中一棵子樹不是BSF樹，則傳回false
		if(!isBST(root.getLeft()) || !isBST(root.getRight()))
			return false;
    	return true;
    }
           

改進的算法

思路：

因為對于一棵二叉搜尋樹來說，其中序周遊之後是一個遞增的有序序列，是以隻要在中序周遊過程中判斷目前結點是否都大于前面所通路的的值就OK了，直到周遊結束，我們可以利用一個pre變量來儲存前驅結點，并初始化pre為盡可能小的值。

反過來講，如果存在一個目前結點小于其前驅結點，那麼這棵樹就不是二叉搜尋樹。

此算法的時間複雜度為O（n），空間複雜度為O（n）。

Java版本實作

//判斷給定的二叉樹是否為BST樹的改進算法
    boolean isBSTOfBetter(BinaryTreeNode<T> root,int pre) {
    	if(root == null)
    		return true;
    	//如果有一棵左子樹不是BST樹則傳回false
    	if(!isBSTOfBetter(root.getLeft(), pre))
    		return false;
    	//如果目前結點小于前驅結點則傳回false
    	if((int)root.getData() < pre)
    		return false;
    	//更新前驅結點
    	pre = (int) root.getData();
    	//如果有一棵右子樹不是BST樹則傳回false
    	if(!isBSTOfBetter(root.getRight(), pre))
    		return false;
    	return true;
    }