题目链接: 二叉搜索树中第 K 小的元素

二叉搜索树的性质

  1. 左子树性质
    任意节点的左子树中所有节点的值 都小于 该节点的值。
  2. 右子树性质
    任意节点的右子树中所有节点的值 都大于 该节点的值。
  3. 递归性
    左子树和右子树本身也必须是二叉搜索树（即递归满足以上两条性质）。
  4. 没有重复节点（通常情况）
    标准的 BST 通常假设节点值唯一（不包含相等的值）。若有重复值，可以约定放在左子树或右子树（实践中常扩展定义）。
  5. 中序遍历是有序序列
    对 BST 进行中序遍历（左 → 根 → 右），得到的结果是一个 严格递增 的序列。这是 BST 最重要的一个实用性质。

思路

本题主要考察第五个性质, 中序遍历二叉树,并计数,即可得到第k小的节点值.

参考代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public int cnt=0;
    public int ans=-1;
    public int kthSmallest(TreeNode root, int k) {
        inorder(root,k);
        return ans;
    }
    //中序遍历
    public void inorder(TreeNode root,int k)
    {
        if(root==null||ans!=-1) return ;
        inorder(root.left,k);
        cnt++;
        if(cnt==k)
        {
            ans=root.val;
            return;
        }
        inorder(root.right,k);
    }
}

易错

刚写的时候写错了,找不出自己错哪里了,原来我把cnt当做函数形参传递了(初始为0),其他没变化.

为啥这样不对?

因为java只有值传递, 每一次进入递归函数 对cnt++的操作只会在当前栈帧有效, 对其他栈帧的cnt没影响..

模拟一下,当初次进入递归函数, cnt=0,会一直向左子树递归,然后就导致一路上的cnt都是0, 就导致返回的时候,cnt变化了, 但是那一路上的cnt还都是0. 就导致错误了 。

下面是另一个版本(ai):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int kthSmallest(TreeNode root, int k) {
        return inorder(root, new int[]{k});
    }
    private int inorder(TreeNode root, int[] k) {
        if (root == null) return -1;  // 未找到
        
        // 左子树
        int leftResult = inorder(root.left, k);
        if (k[0] == 0) return leftResult;  // 已经在左子树找到
        
        // 当前节点
        k[0]--;  // 相当于 cnt++，但这里直接消耗 k
        if (k[0] == 0) return root.val;
        
        // 右子树
        return inorder(root.right, k);
    }
}

__END__