BST

validate BST
inorder successor of BST
BST Iterator
closest value of BST I II(难题)
Unqiue BST I II 充分利用BST的性质！！
Largest BST subtree
Delete Node in BST
Convert BST to Greater Tree (好题)
Recover BST

Validate BST

这题有个技巧，要设两个全局变量
- boolean firstNode = true;
- int prev = Integer.MIN_VALUE;
然后就是关键一步if(!firstNode && prev >= root.val) return false;

public class Solution {
    private boolean firstNode = true;
    private int prev = Integer.MIN_VALUE;
    public boolean isValidBST(TreeNode root) {
        //inorder traversal incremental
        if(root == null) return true;
        if(!isValidBST(root.left)) return false;
        if(!firstNode && prev >= root.val) return false;
        firstNode = false;
        prev = root.val;
        if(!isValidBST(root.right)) return false;
        return true;
    }
}

还有一种不用设全局变量的做法, recursion
建立private boolean isBST(TreeNode root, Integer min, Integer max)
并且初始化isBST(root, null,null)
这个用的是Divide & Conquer的思路，更简单

public class Solution {
    public boolean isValidBST(TreeNode root) {
        return isBST(root, null, null);
    }
    private boolean isBST(TreeNode root, Integer min, Integer max){
        if(root == null) return true;
        if(min != null && root.val <= min) return false;
        if(max != null && root.val >= max) return false;

        return isBST(root.left, min, root.val) && isBST(root.right, root.val, max) ;
    }
}

Inorder Successor of BST

这题首先想到一个naive的解法，就是首先判断p有没有right child
如果有的话，直接找p.right里的leftmost child
如果没有的话，就需要从root遍历寻找到p,同时需要用一个succ纪录目前遍历过的比它大的最小的数，也就是successor
只有当p.val < root.val的时候才更新succ = root;
写出来的代码虽然不算慢，但是好长好丑,只打败21%

public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
        //if p has right child, return the leftmost of this right child tree
        if(p.right != null){
            TreeNode res = p.right;
            while(res.left != null){
                res = res.left;
            }
            return res;
        }
        TreeNode succ = null;
        while(root != null){
            if(root.val < p.val){
                root = root.right;
            }else if(root.val > p.val){
                 succ = root;//只有当root.val > p.val的时候才更新succ = root
                root = root.left;
            }else{
                return succ;
            }
        }
        return succ;
    }

后来想想，发现可以直接遍历查找这棵树的同时判断root.val和p.val，来确定朝left走还是right
代码简洁，实际面试过程中不太好想

public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
        TreeNode succ = null;
        while(root != null){
            if(p.val < root.val){
                succ = root;
                root = root.left;
            }else{
                root = root.right;
            }
        }
        return succ;
    }

所有关于tree的题目都要想着用iterative 和recursive来解决

这题inOrderSuccesscor(TreeNode root, TreeNode p)返回的是在root这棵BST里面的P的successor
下面关键就是判断root.val和p.val和p.val和p.val的关系
p.val >= root.val的意义在于，我们可以确定p的successor肯定不可能是root,而且只可能在root.right这棵子树里，所以把这个任务交给root.right去处理。
只有在p.val < root.val的时候，root才有可能是p的successor,注意是有可能！
那什么时候root是p的sucessor呢？那就是当root.left里找不到p的successor的时候，也就是inOrderSuccessor(root.left, p) == null的时候，具体意义就是root.left子树里没有node的值> p.val。
当然如果inOrderSuccessor(root.left, p )返回不为空，也就意味着在root.left里找到了p的successor, 所以直接返回这个值
搞清楚p = 9和p = 11的例子

public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
        if(root == null) return null;
        if(p.val >= root.val){
            return inorderSuccessor(root.right, p);
        }else{
            TreeNode left = inorderSuccessor(root.left, p);//find the leftmost child
            return left != null ? left : root;
        }

    }

BST Iterator

inorder traversal
先找到left most child,也就是最小的点node,这个过程中的node都放进stack

然后cur指向node.right

public class BSTIterator {
 private Stack<TreeNode> stk = new Stack<>();
 private TreeNode cur;
 public BSTIterator(TreeNode root) {
     cur = root;
 }

 /** @return whether we have a next smallest number */
 public boolean hasNext() {
     return (cur != null || !stk.isEmpty());
 }

 /** @return the next smallest number */
 public int next() {
     while(cur != null) {
         stk.push(cur);
         cur = cur.left;
     }
     cur = stk.pop();
     TreeNode node = cur;
     cur = cur.right;
     return node.val;

 }
}

Closest value of BST

找到离target最近的一个node.val
假设root.val < target,就判断右子树的closestValue b和root.val哪个更接近
如果root.val > target,就判断左子树的closestValue b 和root.val哪个更接近

public int closestValue(TreeNode root, double target) {
        int a = root.val;
        TreeNode child = a < target ? root.right : root.left;
        if(child == null) return a;
        int b = closestValue(child, target);
        return Math.abs(a - target) < Math.abs(b - target) ? a : b;
    }

Closest BST K Values

找到离target最近的K个node.val

Unqiue BST

自己推了一遍，思路是有的
最后公式的总结还需熟练

public int numTrees(int n) {
        //G(i) 表示用1~N的树，以i为root的bst的个数
        //F(n) 表示n个数组成bst的个数
        //G[i] = F[i - 1] * F[n - i]
        //F[n] = G[1] + G[2] + ... + G[n]
        int[] f = new int[n + 1];
        f[0] = 1;//不是0
        f[1] = 1;
        for(int i = 2; i <= n; i++){
            for(int j = 1; j <= i; j++){
                f[i] += f[j - 1] * f[i - j];
            }
        }
        return f[n];
    }

Unique BST II

这题不难想到public List<TreeNode> genTree(int beign, int end)
但是遍历leftSubTree和rightSubTree一开始的确没想到这么做

不错的题目

public class Solution {
 public List<TreeNode> generateTrees(int n) {
     if(n < 1) return new ArrayList<TreeNode>();
     return helper(1, n);
 }
 private List<TreeNode> helper(int begin, int end){
     List<TreeNode> res = new ArrayList<>();
     if(begin > end) {
         res.add(null);
         return res;
     }
     for(int i = begin; i <= end; i++){
         List<TreeNode> leftSubTree = helper(begin, i - 1);
         List<TreeNode> rightSubTree = helper(i + 1, end);

         for(TreeNode left : leftSubTree){
             for(TreeNode right : rightSubTree){
                 TreeNode root = new TreeNode(i);
                 root.left = left;
                 root.right = right;
                 res.add(root);
             }
         }
     }
     return res;
 }
}

Largest Sub BST

https://leetcode.com/problems/largest-bst-subtree/discuss/78891/Share-my-O(n)-Java-code-with-brief-explanation-and-comments

Convert BST to greater Tree

greater tree的性质就是inorder 之后是一个descending order
do ad reverse inOrder traversal and add rightSum to the root.val

class Solution {
    //reverse inorder traversal
    //right, root, left
    int sum = 0;
    public TreeNode convertBST(TreeNode root) {
        convert(root, 0);
        return root;
    }
    private int convert(TreeNode root, int sum) {
        if (root == null) return sum;
        int rightSum =  convert(root.right, sum);
        root.val += rightSum;
        return convert(root.left, root.val);

    }
}

Recover BST

brute force的方法就是inorder traversal, 然后找到两个node, 可以存成global variable
trick在于当我们发现prev.val >= root.val时候如何判断哪个是需要swap的node
这里可以首先check firstNode == null, 如果不空则说明当前root是secondNode

class Solution {
    TreeNode first, second;
    TreeNode prev = new TreeNode(Integer.MIN_VALUE);
    public void recoverTree(TreeNode root) {
        inorder(root);
        int tmp = first.val;
        first.val = second.val;
        second.val = tmp;
    }
    private void inorder(TreeNode root) {
        if (root == null) return;
        inorder(root.left);
        //do something
        if (first == null && prev.val >= root.val) {
            first = prev;
        }
        if (first != null && prev.val >= root.val) {
            second = root;
        }
        prev = root;
        inorder(root.right);
    }
}

follow up可以是要求iterative实现inorder
难点在于要求in place, 那就只能上morris traversal了

PreviousIn place - Morris Traversal NextDelete Node in BST

Last updated 4 years ago

Was this helpful?