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

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

思路：遍历顺序肯定是中序，才能用上搜索树的性质。

  1. 全局记录答案。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    private int ans;
    private int k;

    public int kthSmallest(TreeNode root, int k) {
        this.k = k;
        dfs(root);
        return ans;
    }
	// 左中右遍历，在根节点k--。
    private void dfs(TreeNode node) {
        if (node == null || k <= 0) {
            return;
        }
        dfs(node.left); // 左
        if (--k == 0) {
            ans = node.val; // 根
        }
        dfs(node.right); // 右
    }
}
  1. 向上递归答案。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    int k;
    public int kthSmallest(TreeNode root, int k) {
        this.k = k;
        return dfs(root);
    }
    // 左中右遍历，空节点返回-1表示没找到，如果左边没找到，看一下根节点是不是，然后返回右边的结果(因为不在右边就在上边了)
    int dfs(TreeNode root) {
        if(root == null) {
            return -1;
        }
        int left = dfs(root.left);
        if(left != -1) {
            return left;
        }
        k--;
        if(k == 0) {
            return root.val;
        }
        return dfs(root.right);
    }
}