Tree, BST

• 递归时，要考虑状态可能的不连续性。

• 取左右子树的min / max 之后加上当前节点是最常见的递归结构，保证path自顶向下的连续。

• BST做inorder traversal得到的结果是sorted。

• BST中root的左子树所有点小于root；右子树所有点大于root。

• 一个正确的BST中每一个点都有其取值闭区间，为[左子树max, 右子树min]，最左右两端的点有一端放开区间。

• 维护大小为k的MaxHeap

PriorityQueue<Integer> queue = new PriorityQueue<Integer>(k, Collections.reverseOrder());

Tree类问题中，递归转迭代的常用手法，就是利用尾递归。

Closest Binary Search Tree Value

所谓“最近的点”，可能是parent，可能是child，可能在左边，可能在右边。

• 所以一定要存好prev
• 两边都要探，不要沿着一边硬走。

递归的解法：确保不要去走null的点

public class Solution {
    public int closestValue(TreeNode root, double target) {
        return helper(root, target, root.val);
    }

    private int helper(TreeNode root, double target, int prev) {
        if (root == null) {
            return -1;
        }

        prev = Math.abs(prev - target) > Math.abs(root.val - target) ? root.val : prev;

        if (root.left != null && root.val > target) {
            return helper(root.left, target, prev);
        } else if (root.right != null && root.val < target) {
            return helper(root.right, target, prev);
        }

        return prev;
    }
}

迭代的解法：这样写更简洁, 而且不用考虑node为空的情况。

public class Solution {
    public int closestValue(TreeNode root, double target) {
        int result = root.val;

        while (root != null) {
            if (Math.abs(result - target) > Math.abs(root.val - target)) {
                result = root.val;
            }
            root = root.val > target ? root.left : root.right;
        }

        return result;
    }
}

Validate Binary Search Tree

解法一：postorder traversal，把left child和right child的信息已经当前node的信息汇总，来判断是不是valid bst，然后把这个信息向上传递。

public class Solution {
    public boolean isValidBST(TreeNode root) {
        return helper(root).isBST;
    }

    private ReturnType helper(TreeNode root) {
        if (root == null) {
            return new ReturnType(true, Integer.MAX_VALUE, Integer.MIN_VALUE);
        }

        ReturnType left = helper(root.left);
        ReturnType right = helper(root.right);

        if (!left.isBST || !right.isBST) {
            return new ReturnType(false, 0, 0);
        }

        if (root.left != null && left.max >= root.val || root.right != null && right.min <= root.val) {
            return new ReturnType(false, 0, 0);
        }

        return new ReturnType(true, Math.min(left.min, root.val), Math.max(right.max, root.val));
    }
}

class ReturnType {
    boolean isBST;
    int min, max;

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

解法二：看到bst的题就想下inorder traversal的思路。

public class Solution {
    public boolean isValidBST(TreeNode root) {
        Stack<TreeNode> stack = new Stack<TreeNode>();
        TreeNode current = root, prev = null;

        while (current != null || !stack.isEmpty()) {
            while (current != null) {
                stack.push(current);
                current = current.left;
            }

            TreeNode node = stack.pop();
            if (prev != null && prev.val >= node.val) {
                return false;
            }
            prev = node;
            current = node.right;
        }

        return true;
    }
}

Kth Smallest Element in a BST

这题考察的就是BST的性质，in order = sorted

• follow up1: what if you call this function multiple times?

• • answer: 在解法一中，用hashmap存一下node和其对应的number of left nodes的信息。

• follow up2: what if BST is modified (insert / delete) often?

• • answer: 维护一个max heap。insert好办，如果是发生了delete operation，那就看delete的那个在不在这个max heap里，如果在的话，把这个node从max heap删除。

解法一：binary search solution

public class Solution {
    public int kthSmallest(TreeNode root, int k) {
        int leftNodes = countNodes(root.left);

        if (leftNodes == k - 1) {
            return root.val;
        } else if (leftNodes > k - 1) {
            return kthSmallest(root.left, k);
        } else {
            return kthSmallest(root.right, k - leftNodes - 1);
        }
    }

    private int countNodes(TreeNode root) {
        if (root == null) {
            return 0;
        }

        int left = countNodes(root.left);
        int right = countNodes(root.right);

        return 1 + left + right;
    }
}

解法二：inorder traversal recursive

public class Solution {

    int count = 0;
    int result = 0;

    public int kthSmallest(TreeNode root, int k) {
        inorder(root, k);
        return result;
    }

    private void inorder(TreeNode root, int k) {
        if (root == null) {
            return;
        }

        inorder(root.left, k);
        count++;
        if (count == k) {
            result = root.val;
        }
        inorder(root.right, k);
    }
}

解法三: inorder traversal iterative

public class Solution {
    public int kthSmallest(TreeNode root, int k) {
        Stack<TreeNode> stack = new Stack<TreeNode>();
        TreeNode current = root;
        int count = 0;

        while (current != null || !stack.isEmpty()) {
            while (current != null) {
                stack.push(current);
                current = current.left;
            }

            TreeNode node = stack.pop();
            count++;
            if (count == k) {
                return node.val;
            }
            current = node.right;
        }

        return -1; // never hits
    }
}

Inorder Successor in BST

iterative solution

public class Solution {
    public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
        if (root == null || p == null) {
            return null;
        }

        TreeNode successor = null;

        while (root != null) {
            if (root.val > p.val) {
                successor = root;
                root = root.left;
            } else {
                root = root.right;
            }
        }

        return successor;
    }
}

recursive solution

public class Solution {

    TreeNode successor = null;

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

        if (root.val > p.val) {
            successor = root;
            return inorderSuccessor(root.left, p);
        } else {
            return inorderSuccessor(root.right, p);
        }
    }
}

Convert Sorted Array to Binary Search Tree

利用BST inorder = sorted的性质

在BST里多用区间的思想思考问题

解法一：recursive solution

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

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

    private TreeNode helper(int[] nums, int start, int end) {
        if (start > end) {
            return null;
        } else if (start == end) {
            return new TreeNode(nums[start]);
        }

        int mid = (start + end) / 2;
        TreeNode root = new TreeNode(nums[mid]);
        root.left = helper(nums, start, mid - 1);
        root.right = helper(nums, mid + 1, end);

        return root;
    }
}

解法二：iterative solution， 建一个Tuple类，存下start index, end index的信息

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

        int start = 0, end = nums.length - 1;
        int mid = (start + end) / 2;
        TreeNode root = new TreeNode(nums[mid]);
        Queue<Tuple> queue = new LinkedList<Tuple>();
        queue.offer(new Tuple(root, start, mid, end));

        while (!queue.isEmpty()) {
            Tuple t = queue.poll();
            if (t.start <= t.mid - 1) {
                int leftStart = t.start, leftEnd = t.mid - 1;
                int leftMid = (leftStart + leftEnd) / 2;
                TreeNode left = new TreeNode(nums[leftMid]);

                t.node.left = left;
                queue.offer(new Tuple(left, leftStart, leftMid, leftEnd));
            }
            if (t.mid + 1 <= t.end) {
                int rightStart = t.mid + 1, rightEnd = t.end;
                int rightMid = (rightStart + rightEnd) / 2;
                TreeNode right = new TreeNode(nums[rightMid]);

                t.node.right = right;
                queue.offer(new Tuple(right, rightStart, rightMid, rightEnd));
            }
        }

        return root;
    }
}

class Tuple {
    TreeNode node;
    int start, mid, end;

    public Tuple(TreeNode node, int start, int mid, int end) {
        this.node = node;
        this.start = start;
        this.mid = mid;
        this.end = end;
    }
}

Verify Preorder Sequence in Binary Search Tree

• 只给定一个preorder顺序是无法生成唯一binary tree的，也可以生成多个valid BST。

所以这题的题意需要澄清下，正确意思是给定一个preorder sequence，只要这个sequence可以生成一个valid BST，都返回true。

这样我们的判断条件变成了这样，给定一个array如5(123)(678)，第一个元素一定为root，后面的比root小的连续序列为左子树，后面比root大的连续序列为右子树。

左右子树可以为空，但是不能违反BST子树的性质。所以如果>root的连续数组后面又出现了<root的元素，一定为false。

divide conquer，时间复杂度为O(nlogn)

public class Solution {
    public boolean verifyPreorder(int[] preorder) {
        if (preorder == null || preorder.length <= 2) {
            return true;
        }

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

    private boolean helper(int[] preorder, int start, int end) {
        if (end - start <= 1) {
            return true;
        }

        int root = preorder[start];
        int rightChildStart = start + 1;

        for (int i = start + 1; i <= end; i++) {
            if (preorder[i] < root) {
                rightChildStart++;
            } else {
                break;
            }

        }

        for (int i = rightChildStart; i <= end; i++) {
            if (root > preorder[i]) {
                return false;
            }
        }

        return helper(preorder, start + 1, rightChildStart - 1) && helper(preorder, rightChildStart, end);
    }
}

Recover Binary Search Tree

recursive solution O(1) space

public class Solution {

    TreeNode first = null, second = null;
    TreeNode prev = null;

    public void recoverTree(TreeNode root) {
        inorder(root);

        if (first != null && second != null) {
            int temp = first.val;
            first.val = second.val;
            second.val = temp;
        }
    }

    private void inorder(TreeNode root) {
        if (root == null) {
            return;
        }

        inorder(root.left);

        if (prev == null) {
            prev = root;
        } else {
            if (prev.val > root.val) {
                if (first == null) {
                    first = prev;
                    second = root;
                } else {
                    second = root;
                }
            }
            prev = root;
        }

        inorder(root.right);
    }
}

iterative solution: O(h) space

public class Solution {
    public void recoverTree(TreeNode root) {
        TreeNode first = null, second = null, prev = null;

        TreeNode current = root;
        Stack<TreeNode> stack = new Stack<TreeNode>();

        while (current != null || !stack.isEmpty()) {
            while (current != null) {
                stack.push(current);
                current = current.left;
            }

            TreeNode node = stack.pop();
            if (prev == null) {
                prev = node;
            } else {
                if (prev.val > node.val) {
                    if (first == null) {
                        first = prev;
                        second = node;
                    } else {
                        second = node;
                    }
                }
                prev = node;
            }
            current = node.right;
        }

        if (first != null && second != null) {
            int temp = first.val;
            first.val = second.val;
            second.val = temp;
        }
    }
}