二叉搜尋樹

700.二叉搜尋樹中的搜尋

給定二叉搜尋樹（BST）的根節點和一個值。 你需要在BST中找到節點值等于給定值的節點。 傳回以該節點為根的子樹。 如果節點不存在，則傳回 NULL。

例如，

在上述示例中，如果要找的值是 5，但因為沒有節點值為 5，我們應該傳回 NULL。

public TreeNode searchBST(TreeNode root, int val) {
        return search(root,val);

    }
    private TreeNode search(TreeNode root,int val){
        if(root==null){
            return null;
        }
 
        if(val>root.val){
           return search(root.right,val);
        }
        if(val<root.val){
            return search(root.left,val);
        }
        return root;
    }
      

98. 驗證二叉搜尋樹

給定一個二叉樹，判斷其是否是一個有效的二叉搜尋樹。

假設一個二叉搜尋樹具有如下特征：

• 節點的左子樹隻包含小于目前節點的數。
• 節點的右子樹隻包含大于目前節點的數。
• 所有左子樹和右子樹自身必須也是二叉搜尋樹。

　

public boolean isValidBST(TreeNode root) {
      return process(root).isBST;
    }

    // max ,min left.isbst right.isbst left.max<root.val right.min>root.val
    private Info process(TreeNode root){
        if(root ==null){
            return null;// 注意這裡，設為空就好，因為最大值和最小值不好設定，會超限的情況，不好控制，後面用時判空就好
        }
   
        Info left=process(root.left);
        Info right=process(root.right);
        int min=root.val;
        int max=root.val;
        
        if(left!=null){
            min=Math.min(left.min,min);
            max=Math.max(left.max,max);
        }
        if(right!=null){
            min=Math.min(right.min,min);
            max=Math.max(right.max,max);
        }
        boolean isBST=false;
        boolean leftFlag=left==null?true:left.isBST && left.max<root.val;
        boolean rightFlag=right==null?true:right.isBST && right.min>root.val;
        if(leftFlag && rightFlag){
            isBST=true;
        }
        return new Info(max,min,isBST);
    }

    public class Info{
        int max;
        int min;
        boolean isBST;
        public Info(int max,int min,boolean isBST){
            this.max=max;
            this.min=min;
            this.isBST=isBST;
        }
    }
      

　　

530.二叉搜尋樹的最小絕對差

給你一棵所有節點為非負值的二叉搜尋樹，請你計算樹中任意兩節點的差的絕對值的最小值。

示例：

提示：樹中至少有 2 個節點。

思路

題目中要求在二叉搜尋樹上任意兩節點的差的絕對值的最小值。

注意是二叉搜尋樹，二叉搜尋樹可是有序的。

遇到在二叉搜尋樹上求什麼最值啊，內插補點之類的，就把它想成在一個有序數組上求最值，求內插補點，這樣就簡單多了。

遞歸

那麼二叉搜尋樹采用中序周遊，其實就是一個有序數組。

在一個有序數組上求兩個數最小內插補點。

最直覺的想法，就是把二叉搜尋樹轉換成有序數組，然後周遊一遍數組，就統計出來最小內插補點了

 遇到在二叉搜尋樹上求什麼最值，求內插補點之類的，都要思考一下二叉搜尋樹可是有序的，要利用好這一特點。

class Solution {
    int minDiff=Integer.MAX_VALUE;
    TreeNode pre=null;
   
    public int getMinimumDifference(TreeNode root) {
         getMinDiff(root);
         return minDiff;
    }

    private void getMinDiff(TreeNode root){
        if(root==null){
            return;
        }
        getMinDiff(root.left);
        if(pre!=null){
            minDiff=Math.min(minDiff,Math.abs(pre.val-root.val));
        }

        pre=root;
        getMinDiff(root.right);
    
    }
}