二叉搜索树中第k小的元素：中序遍历

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

思考

看到这道题目，想到的应该是如果能把搜索树变成从小到大的数组肯定就好找了，那二叉树中有没有相关特性呢？有的，中序遍历，但是中序遍历有两种

• 隐式

void inOrder(TreeNode root) {
    if (root == null) return;
    inOrder(root.left);   // 左
    visit(root);           // 根
    inOrder(root.right);   // 右
}

• 显式

while (cur != null || !stack.isEmpty()) {
        while (cur != null) {   // 一路向左，节点入栈
        stack.push(cur);
cur = cur.left;
    }
cur = stack.pop();      // 弹出栈顶（访问根）
// 处理 cur
cur = cur.right;         // 转向右子树
}

这里应该用什么呢？那就要看题目要求了，显式手动调用栈，便于中途停下，隐式呢？自动维护，不方便中途停止，复杂度是一样的，那么我们就从题目要求出发，题目需要一个k停下，不需要全部遍历，那就显

代码

import java.util.Stack;

class Solution {
    public int kthSmallest(TreeNode root, int k) {
//        一个技术栈，中序遍历，然后取第k个
        Stack<TreeNode> stack = new Stack<>();
//        定义当前节点
        TreeNode cur = root;
//        判断当前是否还有未处理的节点或者还有暂存的节点
        while (cur != null || !stack.isEmpty()) {
//            当前节点不为空，则将当前节点暂存，并移动到当前节点的左子树
            while (cur != null) {
                stack.push(cur);
                cur = cur.left;
            }
//            当前节点为空，则从暂存栈中取出一个节点，并移动到该节点的右子树,pop抛出栈顶元素
            cur = stack.pop();
//计数器减1
            if (--k == 0) {
                return cur.val;
            }
//            左根右遍历
            cur = cur.right;
        }
//        兜底
        return -1;
    }
}

‍