Problem

Given a binary search tree, write a functionkthSmallestto find thekth smallest element in it.

Note:
You may assume k is always valid, 1 ? k ? BST's total elements.

Follow up:
What if the BST is modified (insert/delete operations) often and you need to find the kth smallest frequently? How would you optimize the kthSmallest routine?

思路一(traverse)

• 中序遍历, 两个全局变量
• 一个记录个数, 一个记录第k个值

    private int count;
    private int res;
    public int kthSmallest(TreeNode root, int k) {
        count = k;
        inorder(root);
        return res;
    }

    private void inorder(TreeNode root) {
        if (root == null) return;
        inorder(root.left);
        count--;
        if (count == 0) {
            res = root.val;
            return;
        }
        inorder(root.right);
    }

思路二(divide & conquer)

• 将bst看成3部分, 左子树, 右子树, 根值
• 如果k在左子树的话, 返回左子树第k个值的结果
• 如果k在右子树的话, 返回右子树第(k- 1 - 左子树个数)的结果
• 否则k便是根值

  public int kthSmallest(TreeNode root, int k) {
        int count = countNodes(root.left);
        if (k <= count) {
            return kthSmallest(root.left, k);
        } else if (k > count + 1) {
            return kthSmallest(root.right, k-1-count); // 1 is counted as current node
        }

        return root.val;
    }

    public int countNodes(TreeNode n) {
        if (n == null) return 0;

        return 1 + countNodes(n.left) + countNodes(n.right);
    }

follow up

• 一开始有点不大懂follow up, 其实意思是, 现在已经能应对修改次数比较多的情况. 如果查询的次数比较多的时候, 怎么办?
• 需要一个集合来记录, 那么思路二便不可以了. 因为会跳过某些数.
• 在思路一的基础上加多一个list. 存储中序的结果.

    private static int count;

    public int kthSmallest(TreeNode root, int k) {
        count = k;
        List<Integer> list = new ArrayList<>();
        inorder(root, list);
        return list.get(k - 1);
    }

    private void inorder(TreeNode root, List<Integer> list) {
        if (root == null) return;
        inorder(root.left, list);
        count--;
        list.add(root.val);
        if (count == 0) {
            return;
        }
        inorder(root.right, list);
    }