230. Kth Smallest Element in a BST[Medium]

230. Kth Smallest Element in a BST

Given the root of a binary search tree, and an integer k, return the kth smallest value (1-indexed) of all the values of the nodes in the tree.

Constraints:

• The number of nodes in the tree is n.
• 1 <= k <= n <= 10^4
• 0 <= Node.val <= 10^4

Example

Input: root = [3,1,4,null,2], k = 1
Output: 1

思路

• BST 当前节点大于左子树且小于右子树
• 中序遍历（左中右）
  利用中序遍历到最左子节点（小），然后回中（中），再去右（大），弹出第k个值

题解

    public int kthSmallest(TreeNode root, int k) {
	// 中序遍历
        Stack<TreeNode> stack = new Stack<>();
        while (!stack.isEmpty() || root != null) {
            while (root != null) {
                stack.push(root);
                root = root.left;
            }
            TreeNode cur = stack.pop();
            if (--k == 0)
                return cur.val;
            root = cur.right;
        }
        return -1;
    }