DX's Digital Garden

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

2 min read

  • 2.11

    • 不能直接返回 root.val 因为原地递归需要返回值

  • 1.26

    • 不用辅助函数，就用全局变量保存结果
class Solution {
    int count=0;
    int ans=-1;
    public int kthSmallest(TreeNode root, int k) {
        if(root==null) return ans;
        kthSmallest(root.left,k);
        count++;
        if(count==k){
            ans = root.val;
        }
        kthSmallest(root.right,k);
        return ans;
    }
}

  • 1.16

    • 依旧想复杂了，没搞懂为啥是中等题？
    • 看了一眼笔记，错了一个点，我想把递归时，把值返回去到主函数，但是有点复杂，直接把 res 放在全局记录即可，辅助函数不用返回值

  • 11.11

    • 想复杂了,就是中序遍历,先到最左子点,然后开始计数与k对比,第一次为啥没头绪呢?
class Solution {
        int count = 0;
        int res = 0;
    public int kthSmallest(TreeNode root, int k) {
        inOrder(root,k);
        return res;
    }
    public void inOrder(TreeNode root,int k){
        if(root==null) return;
        inOrder(root.left,k);
        count++;
        if(count==k){
            res = root.val;
            return;
        }
        inOrder(root.right,k);
    }
}
  • 中序遍历下计算count值,相等时赋值返回

Graph View