Binary Search Tree

Definition

若不为空left subtree （所有节点） < root
若不为空right subtree （所有节点）> root
Duplicate is not allowed
Property:
- inorder traverse is an 不下降 list
- 如果一棵二叉树的中序遍历不是“不下降”序列，则一定不是BST
- 如果一棵二叉树的中序遍历是不下降，也未必是BST
provides the efficient way of data sorting, searching and retriving

Analysis

When validate the BST, the max of the left subtree < root < the min of the right subtree
- introduce result type
build A BST
- O(nlog n)
- worst case, O(n)when the input is sorted and each insert takes up to O(n)
BST上的node操作
- 添加节点
  - O(log n)
- 删除节点
  - Trim a Binary Search Tree
  - 考虑四种情况:
    1. is not in a tree
    2. is a leaf
    3. has only one child - 和LL上删除节点类似，直接指向下一个点,bypass the node
    4. has two children
  - worst case is O(log N)
- searching
  - O(h) or O(log N)

BST Iterator
- 理解是stack结构，因为root会比left leaf更晚pop，所以选择stack
- 当smallest pop以后，需要加入stack是他的right sub，因为此时已经不可能有left sub了
tips
- 递归的时候，要考虑状态的不连续性，比如BST中的差值最大或者最小，并不一定是在相邻的level里

Questions

Binary Search Tree Iterator

BST -> inorder -> stack，用堆来保存
每次只需要把这个点及其left subtree都加入stack

public class BSTIterator {
    private Stack<TreeNode> stack;

    public BSTIterator(TreeNode root) {
        this.stack = new Stack<>();
        if (root != null) {
            addToStack(root);
        }        
    }

    /** @return whether we have a next smallest number */
    public boolean hasNext() {
        return !stack.isEmpty();
    }

    /** @return the next smallest number */
    public int next() {
        TreeNode node = stack.pop();
        //add the node's right to the stack
        if (node.right != null)
            addToStack(node.right);        
        return node.val;
    }

    public void addToStack(TreeNode root) {
        TreeNode node = root;
        while (node != null) {
            stack.push(node);
            node = node.left;
        }
    }
}

Convert Sorted Array to Binary Search Tree

要BST平衡，需要使得每个节点的左右子树大小尽可能接近。（排法可能不固定）所以可以取排序队列中间数字为根节点，肯定会满足左子树<中间<右子树

注意越界的检查

class Solution {
    public TreeNode sortedArrayToBST(int[] nums) {
        if (nums == null || nums.length == 0) return null;

        return helper(0, nums.length - 1, nums);
    }

    public TreeNode helper(int start, int end, int[] nums) {
        if (start > end)
            return null;
        int mid = (start + end) / 2;
        TreeNode root = new TreeNode(nums[mid]);
        root.left = helper(start, mid - 1, nums);
        root.right = helper(mid + 1, end, nums);
        return root;
    }
}

O(n), O(log n) - 即树的高度？？

Convert Sorted List to Binary Search Tree

同样是二分，但是由于是LL，无法用O(1)取得中点，所以需要考虑快慢指针来取中点

需要用中点前的一个指针，在findmid时，保留preSlow
分割LL，preSlow.next = null
如果不想破坏原来的LL结构，考虑加入position

public class Solution {
    /*
     * @param head: The first node of linked list.
     * @return: a tree node
     */
    public TreeNode sortedListToBST(ListNode head) {
        // write your code here
        if (head == null) return null;
        if (head.next == null) return new TreeNode(head.val);

        ListNode mid = findmid(head);

        TreeNode root = new TreeNode(mid.val);
        root.left = sortedListToBST(head);
        root.right = sortedListToBST(mid.next);
        return root;
    }

    public ListNode findmid(ListNode head) {
        ListNode slow = head;
        ListNode preSlow = head;
        ListNode fast = head;

        while (fast != null && fast.next != null) {
            preSlow = slow;
            slow = slow.next;
            fast = fast.next.next;
        }

        //cut off the list
        preSlow.next = null;
        return slow;
    }
}

Inorder Successor in BST

最直接的办法是inorder traverse，这里可以适用于所有的binary tree。实现中，引入一个flag来确认在当前层循环的时候，遇到了P，则根据inorder的特点，如果P点有右子树，那么在下一次循环中，一定能获得这个右子树最左边的点。如果没有右子树，那么返回的就是stack中的最上面一个点，即为P的parent节点

public class Solution {
  public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
      Stack<TreeNode> stack = new Stack<TreeNode>();
      TreeNode cur = root;
      boolean reachedP = false;

      while(cur != null || !stack.isEmpty()){
          while(cur != null){
              stack.push(cur);
              cur = cur.left;
          }
          TreeNode node = stack.pop();
          if(reachedP) return node;
          if(node == p) reachedP = true;

          cur = node.right;
      }
      return null;
  }
}

由BST的特点，我们可以考虑直接利用值的大小进行比较，不需要借助stack或者用一个数组保存inorder
- 这里根据root和p的大小关系可以知道successor可能在左侧或者右侧，如果在右侧则很简单直接进入下一个递归即可。要是在左侧，则可能存在两种情况，successor在左子树上，或者当p在左子树的最右节点时候，successor是原先的root节点。这里用一个null的返回值handle这个情况

public TreeNode successor(TreeNode root, TreeNode p) {
  if (root == null)
    return null;

  if (root.val <= p.val) {
    return successor(root.right, p);
  } else {
    TreeNode left = successor(root.left, p);
    return (left != null) ? left : root;
  }
}
//可以进一步优化，即我们知道对于p>root的情况，我们可以不断向右直到root > p为止。此时p必定在root的左子树上
public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
    while (root != null && root.val <= p.val)
        root = root.right;
    if (root == null)
        return null;
    TreeNode left = inorderSuccessor(root.left, p);
    return (left != null && left.val > p.val) ? left : root;
}

BST