LeetCode-每日一题 230. 二叉搜索树中第K小的元素 [Java实现] [极速] [极简]

LeetCode-每日一题 230. 二叉搜索树中第K小的元素 [Java实现] [极速] [极简]

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

示例 1：

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

---

方法一：中序遍历

维护一个索引值，由中序遍历的特点可得当当前遍历项的索引等于k时，该项即为第k个最小值

    private int k;
    private int index = 0;
    private boolean flag = false;
    private TreeNode node = null;

    public int kthSmallest(TreeNode root, int k) {
        this.k = k;
        middleDeepSearch(root);
        return node.val;
    }

    public void middleDeepSearch(TreeNode root) {
        if (flag || root == null) return;
        middleDeepSearch(root.left);
        if (++index == k) {
            flag = true;
            node = root;
        }
        middleDeepSearch(root.right);
    }

                ​​​​​​​        ​​​​​​​        ​​​​​​​