You need to enable JavaScript to run this app. Python二叉树求最大深度代码中标记行调用maxDepth为何能返回深度?
优惠活动
大模型
产品
解决方案
定价
更多

Python二叉树求最大深度代码中标记行调用maxDepth为何能返回深度?

二叉树最大深度递归逻辑解答

1. 先明确递归的基线条件(终止规则)

maxDepth()函数的第一行就定义了终止逻辑:如果传入的节点是None,直接返回0。也就是说,当递归到叶子节点的左/右空位的时候,会立刻返回0作为这一分支的深度基准。

2. lDepth和rDepth的赋值逻辑

你标记的#HERE处的递归调用不会立刻返回值,而是会完整执行完传入的子节点对应的maxDepth()调用逻辑后,才会把最终返回的结果赋值给对应变量:

  • lDepth存储的是当前节点的整个左子树的最大深度
  • rDepth存储的是当前节点的整个右子树的最大深度
    拿到两个子树的深度后,取更大的那个值加1(加的1对应当前节点本身的层级),就得到了以当前节点为根的子树的最大深度,再向上层返回。

3. 用测试用例走一遍完整流程,你就清楚怎么计算总深度了

测试用例的树结构如下:

1(根节点)
      /   \
     2     3
    / \
   4   5

调用maxDepth(根节点1)的完整执行顺序:

  1. 根节点1不是None,先执行lDepth = maxDepth(节点2),进入节点2的调用逻辑
  2. 节点2不是None,先执行lDepth = maxDepth(节点4),进入节点4的调用逻辑
  3. 节点4不是None,先执行lDepth = maxDepth(节点4.left),节点4的左是None,返回0 → 节点4的lDepth=0
  4. 节点4再执行rDepth = maxDepth(节点4.right),节点4的右是None,返回0 → 节点4的rDepth=0
  5. 节点4取大值0加1,返回1 → 这个1就赋值给节点2的lDepth
  6. 节点2再执行rDepth = maxDepth(节点5),节点5的左右都是None,最终返回1 → 节点2的rDepth=1
  7. 节点2取大值1加1,返回2 → 这个2就赋值给根节点1的lDepth
  8. 根节点1再执行rDepth = maxDepth(节点3),节点3的左右都是None,最终返回1 → 根节点1的rDepth=1
  9. 根节点1取大值2加1,返回3 → 就是最终打印的树高度

整个过程是先自顶向下递归到最底层的叶子节点,再自底向上逐层返回计算好的子树深度,最终得到整棵树的最大深度。

内容的提问来源于stack exchange,提问作者Justin Yoon

相关产品推荐
方舟 Agent Plan

超全模态模型 × Harness 升级,最新支持 Deepseek-V4.1-Flash、GLM-5.3 系列、Doubao-Seedream-5.0-pro、Kimi-K3 (部分), 限时 9.9 元起

最近更新时间:2026.10.18 02:36:04