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了