从简单二叉树问题重新来看深度优先搜索

矫情吗；* 2022-10-02 12:52 108阅读 0赞

点击蓝色“五分钟学算法”关注我哟

加个“星标”，一起学算法

![640][]

### 前言 ###

对于一般的二叉树问题，我们总能想到的是**深度优先搜索**这个算法，继续想下去就是**递归**，但是其实对于深度优先搜索，有很多不一样的思考方向和实现细节，在这基础上，我们可以推导、总结出一些其他的高级算法，例如**分治**、**动态规划**等等，把这些算法联系在一起，更有助于我们理解一些核心的、本质的问题。

接下来通过 LeetCode 第 104 号问题（二叉树的最大深度）来重新来看深度优先搜索。

### 题目描述 ###

给定一个二叉树，找出其最大深度。

二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。

说明: 叶子节点是指没有子节点的节点。

示例：  
给定二叉树 `[ 3 , 9 , 20 , null , null , 15 , 7 ]`，

3   / \  9  20    /  \   15   7
      9  20
        /  \
       15   7

返回它的最大深度 3 。

### 题目分析 ###

给定一个二叉树，求这个二叉树的最大深度，一道很简单的二叉树问题，题目一理解，我们很容易就知道，我们要递归去求解，但是这里还是需要思考的是，**是不是这道题就一种递归思路**？

递归实现的代码往往非常简洁，但是仅仅是一个地方的细微差别，反应出来的是两种完全不一样的思路。

我们一起来看看！

### 不同解法分析 ###

最开始做这道题，我想的非常简单，思路是：把整个二叉树遍历一遍，每个节点都记录一下当前的深度，然后对比求出最大深度即可。于是我写出了下面的代码：

private int max = 1;public int maxDepth(TreeNode root) {    if (root == null) {        return 0;    }    helper(root, 1);    return max;}private void helper(TreeNode root, int currentDepth) {    if (root == null) {        return;    }    max = Math.max(max, currentDepth);    helper(root.left, currentDepth + 1);    helper(root.right, currentDepth + 1);}int max = 1;
    public int maxDepth(TreeNode root) {
        
        if (root == null) {
        
            return 0;
        }
    
        helper(root, 1);
    
        return max;
    }
    
    private void helper(TreeNode root, int currentDepth) {
        
        if (root == null) {
        
            return;
        }
    
        max = Math.max(max, currentDepth);
    
        helper(root.left, currentDepth + 1);
        helper(root.right, currentDepth + 1);
    }

你可以看到这里我定义了一个全局变量 max 来记录当前访问过的所有节点中的最大深度，最后遍历完所有节点，max 就是题目要求的解。

这么做从时间空间复杂度分析其实都没有啥毛病，但是这么写确实会让代码变得有点冗余，经过思考之后，改进得到下面的代码：

public int maxDepth(TreeNode root) {    if (root == null) {        return 0;    }    int left = maxDepth(root.left);    int right = maxDepth(root.right);    return Math.max(left, right) + 1;}
        if (root == null) {
        
            return 0;
        }
    
        int left = maxDepth(root.left);
        int right = maxDepth(root.right);
    
        return Math.max(left, right) + 1;
    }

这里没有定义额外的全局变量或者辅助函数，递归和之前不同的点仅仅是 “更新值” 先后的问题，而且有一点特别重要的是这里的递归是带返回值的，之前的递归是不带返回值的。

那这说明什么呢？

是说明带返回值的递归一定就比不带返回值的递归更优吗？

其实不是，我们要根据具体情况具体分析。

针对这道题，这两种解法确实第二种来的更为简洁，但是明白思路更加的重要。

第一种的思路是有点类似**遍历**，但是这里用的是递归去遍历，并不是我们通常使用的 for 循环，**每到一个树节点就去做一下相应的记录，然后去到下一个树节点做类似的记录，最后把所有的记录汇总就是我们要的答案**。

第二种思路其实就是**分治**，它的核心是**先分再合**，每个节点只负责分跟合，这里的分就是当前树节点如果有子节点就分下去，合是指将子节点的结果以及当前的值进行统一、合并。

你可能会觉得分治就一定比之前的递归遍历更优，先别急着下这个结论，看看[树的中序遍历][Link 1]吧。

思考一下，试着用两种不同的思路去解，相信你会得出和这道题完全相反的结论。

### 思路总结 ###

之前做了挺多的深度优先相关的算法题，像是排列问题，组合问题，N 皇后问题，这些题目都是回溯的思想，条件满足就更新，你很少会去关注当前层和上面一层的联系。

这里的递归也不需要任何的返回值，原因很简单，每一层不需要向上一层反应情况，操作都是基于全局变量或者堆内存的。

但是反观**分治**则情况大不相同，可以举一个我们工作生活中的例子来加以说明：

老板            /  |   \          经理 ...  经理         / | \    /  |  \      员工...员工 员工...员工
              经理 ...  经理
             / | \    /  |  \
          员工...员工 员工...员工

这里一个公司只有一个老板，老板管理着很多的部门，每接到项目，老板都会将这些项目交给不同的部门去做，我们这里假设部门之间相互没有联系（分治算法中不存在重复子问题），每个部门由一个经理来负责，经理会将项目拆分成小任务并分配给不同的员工去处理，到这里，分配就结束了。

员工做完了分配的任务后，向上汇报情况，经理将所有员工汇报的情况整合，继续向上汇报，最后老板根据所有部门经理汇报的情况来产生出公司的策略，也就是最后的解。

这个例子很好的解释了分治算法的思想，不一样的是，这个例子中的员工、经理、老板做的是不一样的事情，但是分治算法会更加的简单，每一层做的事情都是一样的，只是根据子问题得到的数据不一样，因而结果就会不一样。

你可以看到分治其实就是**先分再合，自底向上传递结果的过程**。因为要传递结果，所以递归函数往往就需要有返回值，但是这并不绝对，像**快速排序**这样利用分治思想的算法的递归函数就没有返回值，这是因为它的结果都会记录在同一个数组中。

### 延伸 ###

看完上面的内容你可能会有一个疑问，是不是深度优先搜索必须依靠递归来实现？

其实并不是，函数递归本质上是函数调用函数自己，在系统的底层，我们借助的是函数栈来保存之前的函数，也就是上一层的内容，如果不使用递归，那么就是说我们不能依靠系统为我们提供的函数栈，因此我们需要手动建立一个栈来保存上一层需要的内容，对于这道简单的二叉树问题，代码如下：

public int maxDepth(TreeNode root) {    if (root == null) {        return 0;    }    Stack<TreeNode> stackTree = new Stack<>();    Stack<Integer> stackDepth = new Stack<>();    stackTree.push(root);    stackDepth.push(1);    int max = 1;    while (!stackTree.isEmpty()) {        TreeNode curNode = stackTree.pop();        int curDepth = stackDepth.pop();        if (curNode.left != null) {            stackTree.push(curNode.left);            stackDepth.push(curDepth + 1);        }        if (curNode.right != null) {            stackTree.push(curNode.right);            stackDepth.push(curDepth + 1);        }        if (curNode.left == null && curNode.right == null) {            max = Math.max(max, curDepth);        }    }    return max;}
        if (root == null) {
        
            return 0;
        }
    
        Stack<TreeNode> stackTree = new Stack<>();
        Stack<Integer> stackDepth = new Stack<>();
    
        stackTree.push(root);
        stackDepth.push(1);
    
        int max = 1;
        while (!stackTree.isEmpty()) {
        
            TreeNode curNode = stackTree.pop();
            int curDepth = stackDepth.pop();
    
            if (curNode.left != null) {
        
                stackTree.push(curNode.left);
                stackDepth.push(curDepth + 1);
            }
    
            if (curNode.right != null) {
        
                stackTree.push(curNode.right);
                stackDepth.push(curDepth + 1);
            }
    
            if (curNode.left == null && curNode.right == null) {
        
                max = Math.max(max, curDepth);
            }
        }
    
        return max;
    }

这里我用了两个栈的原因是有两个变量需要保存，一个是节点，另一个是节点对应的深度，当然你也可以把他们合二为一作为一个新的 Object。

**其实在普通的深度优先搜索算法的基础之上，我们也可以看到动态规划的影子**。

一般的深度优先搜索是对之前的子问题的结果不进行保存的。

就拿这道题为例子，当你得到最后的解的时候，这时你只知道整颗树的最大深度，但是你并不知道左子树，以及右子树的最大深度，想要知道的话，就得重新再针对左子树或者右子树深度优先搜索走一遍，但是，其实你之前计算整颗树的最大深度的时候，已经将左子树和右子树的最大深度计算过了，因为（maxDepth = Max(leftMaxDepth, rightMaxDepth)）+ 1。

如果我们用一个数据结构，比如数组或者散列，去记录这些子问题的解，用到的时候直接去这些数据结构中对应着找，**那么这样的思想就是动态规划**，只是这时它是以递归的形式呈现在这里。

当然在这道题当中，记不记录并没有区别，因为没有重复的子问题，换句话说就是除根节点外，一个节点有且仅有一个父节点。

补充一下动态规划类问题的思路步骤：

1.  暴力的深度优先搜索
2.  画出/思考出问题和子问题的关系，看有没有重复子问题
3.  如果有重复子问题，考虑增加记忆化的数据结构
4.  据此，思考动态规划的状态和递推方程
5.  实现动态规划

这些步骤并不是对于每到题都要走完的，对于像排列、组合这类问题到第二步就结束了，但是对于很多动态规划问题我们需要一直走完五个步骤，虽然繁琐了些，但是确实可以加强我们方向和思路。

**动态规划问题怕就怕在没有思路，没有思路就会寸步难行**。

### 总结 ###

整体来看，深度优先搜索的涵盖面确实太广了，一方面是因为它比较好的和递归进行了结合，另一方面是借助它，很多其他算法的思想得到了体现。

如果看到这里你对优先搜索还感兴趣的话，不妨再点进去看看这一篇文章：[几道和「广度优先搜索」有关的算法面试题][Link 2]

![640][640 1]

![640?wx\_fmt=png][640_wx_fmt_png]

**原 创 热 文 推 荐**

☞[毕业十年后，我忍不住出了一份程序员的高考试卷][Link 3]

[☞][Link 4][一道腾讯面试题：厉害了我的杯][Link 5]

[☞][Link 6][十大经典排序算法动画与解析，看我就够了][Link 7]

[☞][Link 6][这或许是东半球分析十大排序算法最好的一篇文章][Link 8]

[☞][Link 6][面试官，我会写二分查找法！对，没有 bug 的那种！][bug]

![640?wx\_fmt=png][640_wx_fmt_png 1] 你点的每个“在看”，我都认真当成了喜欢

[640]: /images/20220112/cdaa0bac7ce9429b910e6cf01210fbe7.png
[Link 1]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg==&mid=2247483853&idx=1&sn=94cd4b4ee8dc2268290a72334c6af57b&chksm=fa0e6e4ccd79e75a41a6b78397b80cdfccda332823874475b516f997f89e786488599fc5cc1e&scene=21#wechat_redirect
[Link 2]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg==&mid=2247485046&idx=1&sn=76bec8ca58817986ebedd6a2e2421725&chksm=fa0e69f7cd79e0e14d9a5db76633fc66edb7d93955c845586c14e710174897d06e96bdd1e24d&scene=21#wechat_redirect
[640 1]: /images/20220112/52c488b9521b4bda9decfb5806ff858a.png
[640_wx_fmt_png]: /images/20220112/86f8ae05fe87411b8b283d9ea034a9da.png
[Link 3]: https://blog.csdn.net/dQCFKyQDXYm3F8rB0/article/details/91488249
[Link 4]: http://mp.weixin.qq.com/s?__biz=MzA5MzY4NTQwMA==&mid=2651011536&idx=3&sn=fd5ff61a84fe2180a7c21d15acf71659&chksm=8bad8a27bcda03319570ae23d05392d287390a51ca94014422dd199450b25f43467aaaedb59e&scene=21#wechat_redirect
[Link 5]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg==&mid=2247484557&idx=1&sn=739d80488fe1169a9c9ca26ecfcdfba6&chksm=fa0e6b0ccd79e21a1c2b0d99db69f6206cddddfe2367742e9de1d7d17ec35a5ce29fa4e30d63&scene=21#wechat_redirect
[Link 6]: http://mp.weixin.qq.com/s?__biz=MzA5MjcxNjc2Ng==&mid=2650560116&idx=1&sn=f9e86fa3e7b15624177b29ef1a785be4&chksm=88601dc5bf1794d30fd595d413491da189584b44fd2b2e5e40c665e58760e162616585811647&scene=21#wechat_redirect
[Link 7]: https://blog.csdn.net/dQCFKyQDXYm3F8rB0/article/details/87910210
[Link 8]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg==&mid=2247485556&idx=1&sn=344738dd74b211e091f8f3477bdf91ee&chksm=fa0e67f5cd79eee3139d4667f3b94fa9618067efc45a797b69b41105a7f313654d0e86949607&scene=21#wechat_redirect
[bug]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg==&mid=2247485240&idx=1&sn=fbccc747b2e8558c6478171709005ff9&chksm=fa0e68b9cd79e1af5ab68d42adea0b24c7d4867069091df9e95b6f20ab57b69c4e38994a36be&scene=21#wechat_redirect
[640_wx_fmt_png 1]: /images/20220112/46ed3d72982a41a9b0ec01e5ddb91e75.png