二叉搜索树中第 K 小的元素

给定一个二叉搜索树的根节点 root ，和一个整数 k ，请你设计一个算法查找其中第 k 小的元素（从 1 开始计数）。

示例 1：

输入：root = [3,1,4,null,2], k = 1
输出：1

示例 2：

输入：root = [5,3,6,2,4,null,null,1], k = 3
输出：3

提示：

树中的节点数为 n 。
1 <= k <= n <= 104
0 <= Node.val <= 104

题解：

定义一个实例变量来记录当前是访问的第几个节点，中序遍历找到第 K 个后元素返回即可

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 * int val;
 * TreeNode left;
 * TreeNode right;
 * TreeNode() {}
 * TreeNode(int val) { this.val = val; }
 * TreeNode(int val, TreeNode left, TreeNode right) {
 * this.val = val;
 * this.left = left;
 * this.right = right;
 * }
 * }
 */
class Solution {
    int kth, ans;

    public int kthSmallest(TreeNode root, int k) {
        kth = k;
        ans = 0;
        helper(root);
        return ans;
    }

    // --- 中序遍历
    public void helper(TreeNode node) {
        if (node == null || kth < 0)
            return;
        helper(node.left);
        if (--kth == 0)
            ans = node.val;
        helper(node.right);
    }
}

迭代版本：

迭代版本的先序遍历和中序遍历唯一的区别就是，先序遍历是在入栈时访问，而中序遍历是在出栈时访问；迭代的优势是，无需额外的实例变量，但是代码的简洁程度不如递归方式。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 * int val;
 * TreeNode left;
 * TreeNode right;
 * TreeNode() {}
 * TreeNode(int val) { this.val = val; }
 * TreeNode(int val, TreeNode left, TreeNode right) {
 * this.val = val;
 * this.left = left;
 * this.right = right;
 * }
 * }
 */
class Solution {

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