Given a binary search tree, write a function kthSmallest to find the kth smallest element in it.

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

    Example 1:

    1. Input: root = [3,1,4,null,2], k = 1
    2.    3
    3.   / \
    4.  1   4
    5.   \
    6.    2
    7. Output: 1

    Example 2:

    1. Input: root = [5,3,6,2,4,null,null,1], k = 3
    2.        5
    3.       / \
    4.      3   6
    5.     / \
    6.    2   4
    7.   /
    8.  1
    9. Output: 3

    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?

    题意

    找到BST中第k小的数。

    思路

    BST的中序遍历是递增序列，因此可以先进行中序遍历再找到第k小。

    代码实现 - 中序遍历(递归)

    1. class Solution {
    2.     public int kthSmallest(TreeNode root, int k) {
    3.         List<Integer> list = new ArrayList<>();
    4.         preOrder(root, list);
    5.         return list.get(k - 1);
    6.     }
    8.     private void preOrder(TreeNode root, List<Integer> list) {
    9.         if (root == null) {
    10.             return;
    11.         }
    12.         preOrder(root.left, list);
    13.         list.add(root.val);
    14.         preOrder(root.right, list);
    15.     }
    16. }

    代码实现 - 中序遍历(迭代)

    1. class Solution {
    2.     public int kthSmallest(TreeNode root, int k) {
    3.         int count = 0;
    4.         int ans = 0;
    6.         Deque<TreeNode> stack = new ArrayDeque<>();
    7.         TreeNode cur = root;
    8.         while (cur != null || !stack.isEmpty()) {
    9.             while (cur != null) {
    10.                 stack.push(cur);
    11.                 cur = cur.left;
    12.             }
    13.             cur = stack.pop();
    14.             count++;
    15.             if (count == k) {
    16.                 ans = cur.val;
    17.                 break;
    18.             }
    19.             cur = cur.right;
    20.         }
    22.         return ans;
    23.     }
    24. }