leeetcode 104的递归终止条件

Question

bobo老师，关于递归求解二叉树的最大深度这个题目，我还有些不理解递归的终止条件如何设定。比如，题目中说求解“根节点到叶子节点的深度”，其中给出了叶子结点的定义。但是，我们在递归终止条件中并没有用到这个条件？也就是说，我们的递归终止条件只有一个: if(root == null) return 0，并没有单独考虑叶子节点。我第一次遇到这个题目的时候，写了两个终止条件，第二个是 if(root.left == null && root.right == null) return 1。虽然也通过了，但是和您的参考答案相比，第二个条件冗余了。这种区别在做leetcode 111号问题时更明显了，求最低深度时，就不能忽略叶子节点的定义了。所以我想问，如果不多也不少地恰当选取递归终止条件？

Answer 1

liuyubobobo 2022-03-29 03:54:49

我不认为 if(root.left == null && root.right == null) 是冗余。这二者的区别是对叶子节点的定义不同。

if(root == null) 是将每棵树到底的那个空节点当做叶子节点（回忆一下，在我的体系课程中，介绍红黑树的性质的时候，说红黑树的叶子节点一定是黑节点，其实对红黑树叶子的定义，就是采取的这个定义）

而 if(root.left == null && root.right == null) 是将左右子树均为空的节点作为叶子节点。

对叶子节点的定义不同，相应的逻辑就不同。比如，如果最后的空节点是叶子节点，那么空节点的高度就是 0；如果左右子树都为空的节点是叶子节点，那么这个叶子节点的高度就是 1。

但是，他们都能得到正确的答案。

==========

111 号问题同样可以以 if(root.left == null && root.right == null) 为递归终止条件，得到正确的代码。以下代码可 AC。

class Solution {
    
    public int minDepth(TreeNode root) { 
        if(root == null) return 0;
        return dfs(root);
    }
    
    private int dfs(TreeNode node){
        
        if (node.left==null && node.right==null){
            return 1;
        }
        
        int res = Integer.MAX_VALUE;
        if(node.left != null)
            res = Math.min(res, 1 + minDepth(node.left));
        if(node.right != null)
            res = Math.min(res, 1 + minDepth(node.right));
        return res;
    }
}

之所以把递归过程单独做成一个 dfs，是因为这个问题的测试用例中，传来的 root 可能为空。而我们又决定在递归过程中不对 node 为空作为递归终止条件，那么就在递归外面做一下特判。

可以看到，此时 dfs 的递归终止条件就是：if(root.left == null && root.right == null)

==========

至于你问的：如何不多也不少地恰当选取递归终止条件？我不知道。

原因非常简单，什么叫“不多也不少地恰当地...”是没有明确定义的。没有明确定义的问题很难讨论。

我只能说，一个“经验之谈”是，很多时候，如果你觉得到了递归的“底”，但是对这个“底”的处理有稍微有些复杂的话，可以尝试一下，能不能再往下走一层。

并不是所有的时候都能再往下走一层，也并不是所有的时候再往下走一层就真的变简单了，但这是一个可以尝试的方向。比如在这个问题中，左右子树都为空的叶子其实可以再往下走一层，到一个空节点。

==========

这里再多说两句：（其实我能看出来你的素质很高的，所以下面的话可能对你来说都是废话）

如果你觉得有人总是能“不多也不少地恰当”做好某件事儿，而你不能，大概率**不是**因为这个人知道一个“答案”，你只要也知道了这个答案，不管是一句话，还是一篇文章，就 ok 了。大概率是因为，这个人做这件事儿比你更有经验。

经验是无法转换成语言的，这也正是大多数事情难的原因。可以参考我的公众号文章：https://mp.weixin.qq.com/s/1LHraeRhcYoxY03VS7Riag 

我完全可以理解，在这个例子里，你觉得使用 if(root == null)，似乎代码行数更少，代码更简洁，而使用 if(root.left == null && root.right == null)，似乎代码更多了，更复杂了，冗余了。但我不这么看这个问题。如我所说，在我看来，这二者的核心区别是：定义不同。在不同的定义下，就会产生不同的代码。这一点在我的课程中也经常强调：编写逻辑的首要任务是明确清楚你要写的逻辑中各个变量，函数，模块的语义。一旦这些定义明确了，逻辑是围绕这些定义展开的。（比如印象里关于 comparator 的问题也是你问的，一旦我清晰地告诉了 comparator 的语义，一切逻辑就变得很自然，都是围绕这个语义展开的；但如果你没有清晰这个语义，陷入逻辑的细节中是没有帮助的，就是这个道理。）

一旦你做到了这一点，就算你的代码行数多了一些，但是整体逻辑也应该是很清晰的。与之相反的是，很多人写出的代码又臭又长，其实归根到底是在动手之前，自己逻辑的语义没有想清楚，在写逻辑的过程中，语义在不停地变换，结果越写越复杂，最后搞不好还不能把逻辑正确完整地表达出来。

比如上面我给出的 111 的代码，确实比只用 if(root == null) 做判断更长一些，但是每一行在做什么都是很清晰的，这个代码是很好理解的。在我看来，逻辑“清晰”是一个更重要的标准，而非“代码行数更短”。只要你的逻辑是清晰的，代码不会太复杂；但是很多所谓的“很短”的代码，其实是很晦涩的，并非是工程上最推荐的写法。

如果我是面试官，我更看重你如何解释自己的代码，这背后的逻辑语义是否清晰，而非这个代码有多短。也正是因为如此，我不建议计算机专业的同学背任何的算法模板，或者“奇怪的口诀”，或者使用一些奇怪的原则（比如题目中出现什么关键字就应该怎么样一类的东西）。因为你一旦使用这些东西，你就根本无法深入去思考理解这个问题本身了。（这就是为什么在国内的应试教育下，很多人考分虽然不错，但是其实对知识的掌握很不好，根本不能做到灵活运用。因为那些帮助他们考高分的“技巧”，不是建立在对问题本身的深刻理解上的。）

这些“应试”的手段或许在笔试或者机试的时候还有效，但是在面试过程中，面试官很容易看出来你是在“背”什么东西，还是在组建自己的逻辑，一旦你是“背”的，也很容易戳穿，问题稍微变换一下，你很有可能就蒙了，连思考的路径都没有了。而如果你有自己的思考路径，并且在面试中恰当地展示出来，很有可能即使你不能正确解决一个问题，在面试官心目中，也是完胜的。

因为从职业发展的角度，这些才是一名优秀的工程师最重要的素质，而不是简单地做对一道题而已。

继续加油！：）

• 提问者 讲武德的年轻人 #1

  醍醐灌顶，谢谢bobo老师，看来还要多思考多体会多做题