文章目录LeetCode 104. 二叉树的最大深度前置知识先认识二叉树二叉树节点结构误区第一个误区LeetCode 展示的列表不代表函数收到的是列表root 到底是什么第二个误区能不能通过节点数量直接计算深度第三个问题二叉树应该如何访问DFS 和递归为什么使用 DFS递归到底是怎么运行的一个完整例子结果是如何一层层返回的最容易忽略的问题为什么递归必须 return最开始写出的代码代码优化一为什么不需要 current_node代码优化二为什么可以删除外层判断简化后的代码复杂度分析时间复杂度空间复杂度这道题我真正学到的东西1. LeetCode 展示的结构不代表函数收到的数据结构2. TreeNode 不能像列表一样访问3. 节点数量不能直接决定最大深度4. 递归的核心把大问题拆成相同结构的小问题5. 递归一定需要出口6. DFS 的结果是从下面往上传递的LeetCode 104. 二叉树的最大深度前置知识先认识二叉树这道题是我刚开始接触二叉树时做的所以一开始其实是比较迷茫的。所以推荐在做题之前可以先补充一下二叉树的基础知识菜鸟编程 树形结构二叉树节点结构LeetCode 中已经帮我们定义好了二叉树节点classTreeNode:def__init__(self,val0,leftNone,rightNone):self.valval self.leftleft self.rightright一个节点主要包含三个部分val 当前节点保存的值 left 指向左孩子节点 right 指向右孩子节点例如3 / \ 9 20对应root.val3root.left.val9root.right.val20这里需要注意left和right保存的不是节点的值而是指向另一个TreeNode对象。也就是说root.left得到的是一个新的节点。这个节点里面又继续保存自己的 val 自己的 left 自己的 right所以二叉树实际上是通过节点之间的连接关系组成的。可以简单理解一个节点对象 它指向左孩子的引用 它指向右孩子的引用不断连接起来就是整棵树。一个粗糙的笔记其中self.left None 表示当前节点没有左孩子 self.right None 表示当前节点没有右孩子误区以下是我写的过程中的一些理解错误的地方第一个误区LeetCode 展示的列表不代表函数收到的是列表LeetCode 的示例输入经常写成root [3,9,20,null,null,15,7]所以我一开始下意识认为root 是不是一个列表甚至研究了一遍怎么把列表转换成二叉树队列dequeappend()popleft()如何按照层序把左右孩子填进去后来才发现这道题完全不需要自己进行“列表 → 二叉树”的转换。因为函数定义已经告诉我们defmaxDepth(self,root:Optional[TreeNode])-int:这里的root类型是TreeNode对象而不是listLeetCode 页面显示[3,9,20,null,null,15,7]只是为了方便我们阅读。它表示的是这棵树的序列化形式真正传入函数的是root ↓ 一个 TreeNode 对象 ↓ 通过 left / right 连接整棵树所以我们并不需要自己去构造列表 ↓ 二叉树直接使用这个方式即可root.left root.rightroot 到底是什么这个地方我一开始也比较混乱。这里需要区分TreeNode和rootTreeNode是一种节点类型。类似于一个模板root是一个具体的节点对象。它指向整棵树最上面的根节点。例如3 / \ 9 20那么root.val3而root.left - 9 root.right - 20所以current_noderoot只是让另一个变量也指向同一个节点。并不会创建新的树。换句话说可以记成root 不是整棵树本身而是访问整棵树的入口。只要拿到 root就可以通过root.left root.right root.left.left root.left.right不断地访问下面的节点。比如创建一个rootTreeNode(1)node2TreeNode(2)node3TreeNode(3)node4TreeNode(4)node5TreeNode(5)root.leftnode2 root.rightnode3 node2.leftnode4 node2.rightnode5内存里的关系其实更接近这样root ↓ ┌──────────────┐ │ TreeNode(1) │ │ val 1 │ │ left ────────────────┐ │ right ────────────┐ │ └──────────────┘ │ │ │ │ ↓ ↓ ┌────────┐ ┌────────┐ │ node3 │ │ node2 │ │ val3 │ │ val2 │ │ LNone │ │ left ───────┐ │ RNone │ │ right ───┐ │ └────────┘ └────────┘ │ │ │ │ ↓ ↓ ┌─────┐ ┌─────┐ │ 5 │ │ 4 │ └─────┘ └─────┘第二个误区能不能通过节点数量直接计算深度一开始我还产生过一个想法能不能像列表一样先知道一共有多少个节点然后直接计算有多少层但这个思路在这里是不成立的。因为二叉树的形状并不固定。这道题也没说这个二叉树会是完全二叉树。。例如1 / 2 / 3三个节点深度 3但是1 / \ 2 3同样三个节点深度 2所以节点数量不能直接决定二叉树的最大深度。只有在一些特殊结构例如完全二叉树中节点数量和层数之间才存在固定关系。第三个问题二叉树应该如何访问列表可以foriinrange(len(nums)):通过下标访问。但很显然二叉树不行。因为它不是连续存储的数据结构。不能通过这种访问len(root)root[i]实际上二叉树是通过node.left node.right来不断访问下一层节点。因此遍历二叉树时通常有两种方式DFS深度优先搜索BFS广度优先搜索这道题我最后选择DFS 递归这个知识点可以看这个菜鸟编程 图论结构 后半部分 以及 递归当然后面也有一个相关知识的简单介绍DFS 和递归为什么使用 DFSDFSDepth-First Search深度优先搜索的思路可以简单理解为先沿着一条路径不断往下走直到不能继续再返回上一层去处理其他分支。放到二叉树中就是从当前节点出发继续访问当前节点 ↓ 左子树 ↓ 右子树不过在这道题里重要的不是遍历顺序。而是如何把“求整棵树最大深度”拆成更小的问题。也就是把当前树的最大深度拆成左子树最大深度和右子树最大深度两个更小的问题。于是一个大问题整棵树有多深被拆成了两个结构完全相同的小问题左子树有多深 右子树有多深而这两个问题又可以继续拆。左子树的左子树有多深 左子树的右子树有多深 右子树的左子树有多深 右子树的右子树有多深每一个小问题本质上都还是同一个问题以当前节点为根的这棵树有多深当不断拆分最终遇到空节点 None 时return0然后结果再一层层向上返回。这就是递归。对于一个节点当前节点的最大深度 1 max(左子树最大深度, 右子树最大深度)这里的1表示当前节点自己这一层。这个公式也就是整棵树最大深度 ↓ 求左子树深度 ↓ 求右子树深度 ↓ 取更大的那个 ↓ 加上当前节点这就是递归关系。递归函数实际上是在回答一个问题以当前节点为根节点的这棵树最大深度是多少也就是说dfs(node)不是负责一路数层数。而是负责返回 node 这棵子树的最大深度PSDFS 是一种遍历思路而递归只是实现 DFS 的一种常见写法。递归到底是怎么运行的这是这道题里最需要理解的地方。刚开始接触递归时最容易产生一个疑问为什么函数自己调用自己最后还能得到答案其实递归可以简单地理解成两个过程向下不断把大问题拆成小问题 向上小问题解决后把答案一层层返回在这里我们的递归函数会这样写defdfs(node):ifnodeisNone:return0left_depthdfs(node.left)right_depthdfs(node.right)return1max(left_depth,right_depth)它做的事情其实很简单 如果当前节点为空表示如果当前已经走到了空节点那么这里不存在任何一层。就代表这层不算一个深度所以直接return0例如5 / \ None None对于节点5dfs(5.left) 和 dfs(5.right)都会进入dfs(None)返回0所以dfs(5) 1 max(0, 0) 1也就是说叶子节点的深度就是1因为它本身占据一层。 若是不为空的话就会先询问左孩子left_depthdfs(node.left)再询问右孩子right_depthdfs(node.right)最后根据两个孩子返回的结果计算自己这层的答案return1max(left_depth,right_depth)一个完整例子结果是如何一层层返回的前面说了可以简化为两个过程向下不断把大问题拆成小问题 向上小问题解决后把答案一层层返回这里通过例子解释一下假设3 / \ 9 20 / \ 15 7 调用dfs(3)它不会直接计算。它需要先知道dfs(9)dfs(20) 计算 dfs(9)节点 9 没有孩子dfs(9) 1 max(0,0) 1 计算 dfs(20)继续拆dfs(15) dfs(7) 这是两个叶子节点dfs(15)1 dfs(7)1所以dfs(20) 1 max(1,1) 2最后回到节点 3此时left_depth1right_depth2所以dfs(3) 1 max(1,2) 3最终答案就是3那么整个递归过程3 | ↓ 拆成两个问题 dfs(9) dfs(20) ↓ ↓ 返回1 返回2 ↓ dfs(3) ↓ 返回3可以再简单的记成向下拆问题 向上收答案最容易忽略的问题为什么递归必须 return这是我后来重新写这道题时遇到的问题。一开始容易觉得我已经计算出了深度保存到变量里面不就可以了吗例如defdfs(node):ifnodeisNone:return0left_depthdfs(node.left)right_depthdfs(node.right)depth1max(left_depth,right_depth)看起来depth已经保存了答案。但是问题在于这个变量只存在当前这一层函数里面。下一层递归无法拿到它。例如left_depthdfs(node.left)这里的父节点需要左子树的深度是多少如果子函数没有return那么父节点收到的就是None而不是计算出来的深度。所以递归里面的return作用不是简单地“返回最后结果”, 还有把当前节点计算出来的信息传递给上一层。因此return1max(left_depth,right_depth)实际上是在告诉父节点我的这棵子树最大深度是多少。然后父节点继续利用这个结果计算自己的答案。所以二叉树递归需要去理解 每次调用 dfsnode的时候是在说请告诉我以你为根节点的子树答案是多少。然后孩子返回答案 ↓ 当前节点根据孩子答案计算自己 ↓ 继续返回给父节点最开始写出的代码理解了递归关系以后咱就开始看完整的代码~最开始我写的是classSolution:defdfs(self,node):ifnodeisNone:return0left_depthself.dfs(node.left)right_depthself.dfs(node.right)return1max(left_depth,right_depth)defmaxDepth(self,root:Optional[TreeNode])-int:current_noderootifcurrent_nodeisNone:return0resultself.dfs(current_node)returnresult这份代码可以正常运行。但是这是咱们头一次写所以其实再细看就会发现有一些地方其实是不需要的。代码优化一为什么不需要 current_node这里current_noderoot其实没有必要。因为current_node和root指向的是同一个节点。它并没有创建新的树也没有复制节点。所以可以直接使用root即可。代码优化二为什么可以删除外层判断原本ifcurrent_nodeisNone:return0看起来是在判断空树。但是self.dfs(None)本身已经会执行ifnodeisNone:return0所以外层再次判断其实是重复的。也就是说returnself.dfs(root)已经包含了空树情况。简化后的代码整理以后classSolution:defdfs(self,node):ifnodeisNone:return0left_depthself.dfs(node.left)right_depthself.dfs(node.right)return1max(left_depth,right_depth)defmaxDepth(self,root:Optional[TreeNode])-int:returnself.dfs(root)甚至还可以把dfs()直接写进maxDepth()。不过对于刚开始学习递归来说我觉得把辅助函数单独写出来更容易理解。因为这样可以明确区分maxDepth() 负责接收题目输入 dfs() 负责计算某个节点作为根节点时的最大深度复杂度分析设二叉树共有n个节点。时间复杂度DFS 会访问每一个节点一次。每个节点只进行判断是否为空访问左右孩子比较两个深度所以时间复杂度O(n)空间复杂度递归过程中需要使用调用栈。空间消耗取决于树的高度。如果二叉树退化成链表1 \ 2 \ 3 \ 4递归深度就是n所以最坏情况空间复杂度O(n)如果二叉树比较平衡1 / \ 2 3 / \ 4 5树高约为log n所以递归栈空间约为O(log n)这道题我真正学到的东西1. LeetCode 展示的结构不代表函数收到的数据结构题目展示[3,9,20,null,null,15,7]只是为了方便阅读。真正传入root:Optional[TreeNode]是一个节点对象。需要通过node.left node.right访问其他节点。2. TreeNode 不能像列表一样访问不能root[i]len(root)因为二叉树不是连续存储结构。它是通过节点之间的引用连接起来的。3. 节点数量不能直接决定最大深度因为树的形状不同1 1 | / \ 2 2 3 | 3节点数量相同但是深度不同。所以必须根据树的结构递归计算。4. 递归的核心把大问题拆成相同结构的小问题这道题求整棵树最大深度可以拆成求左子树最大深度 求右子树最大深度然后当前节点深度 1 max(左子树深度, 右子树深度)5. 递归一定需要出口这里ifnodeisNone:return0就是递归停止条件。如果没有这个出口当前节点 ↓ 访问孩子 ↓ 继续访问孩子 ↓ 无限递归6. DFS 的结果是从下面往上传递的这是我做完这道题以后对递归理解最深的一点。可以记成向下不断拆问题 向上不断返回答案dfs(node)并不是自己一路往下数有多少层。而是在回答以这个 node 为根节点的这棵子树最大深度是多少所以left_depthdfs(node.left)其实是在问左孩子以你为根的树有多深而right_depthdfs(node.right)是在问右孩子以你为根的树有多深当两个孩子返回答案以后return1max(left_depth,right_depth)当前节点再计算自己的答案。这也是很多二叉树递归题的核心子节点负责计算子问题 父节点利用子问题结果 最终得到当前问题答案