LeetCode刷题【230】二叉搜索树中第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 小的值，你将如何优化算法？

【中序遍历 双解法】java中序遍历

简单没啥好特别的，搜索树的特性，左小右大，依次遍历的话是从最小的读起的那么对应数组的第k-1位就是所求

class Solution {
    List<Integer> list;
    public int kthSmallest(TreeNode root, int k) {
        list = new ArrayList<>();
        dfs(root);
        return list.get(k-1);
    }

    public void dfs(TreeNode node){
        if (node == null){
            return;
        }
        dfs(node.left);
        list.add(node.val);
        dfs(node.right);
    }
}

如上代码，既然我们知道了由小到大的特性，那么其实就不用遍历整个二叉树了，只要按个遍历了k个节点，将第k个节点返回即可

class Solution {
    int num = 0;
    int k;
    public int kthSmallest(TreeNode root, int k) {
        this.k = k;
        return dfs(root);

    }

    public int dfs(TreeNode node){
        if (node == null){
            return -1;
        }
        int left = dfs(node.left);
        if (left >=0 ){
            return left;
        }
        if (++num == k){
            return node.val;
        }
        int right = dfs(node.right);
        if (right >=0 ){
            return right;
        }
        return -1;
    }
}