剑指offer 54. 二叉搜索树的第k大节点

https://leetcode-cn.com/problems/er-cha-sou-suo-shu-de-di-kda-jie-dian-lcof/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    int res, k;
    public int kthLargest(TreeNode root, int k) {
        this.k = k;
        dfs(root);
        return res;
    }
    void dfs(TreeNode root) {
        if(root == null) return;
        dfs(root.right);
        if(k == 0) return;//这句很巧妙 提前返回
        if(--k == 0) res = root.val;
        dfs(root.left);
    }
}

加了一句 if(k == 0) return; 起到了提前返回的作用，很神奇。

其中我自己想写的话就想为什么要设一个全局变量k呢？为什么不能返回root.val呢？ 就像下面这么写。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
static int dfs(TreeNode root) {
        if(root == null) return 0;
        dfs(root.right);


        

        if(--k == 0)
        {
            res = root.val;
            return root.val;
        }
        dfs(root.left);
        return 0;
    }

但是试了一下发现，返回root.val并不会结束最外面的dfs,最后还要return 0; 所以return的root.val只是跳出了一次dfs,根本无人记录下来啊。所以这里的return 0也好 return root.val也好都没意义了 和return 没区别。真正起作用的还是全局的res记录了root.val。