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不是
None,先执行lDepth = maxDepth(节点2),进入节点2的调用逻辑 - 节点2不是
None,先执行lDepth = maxDepth(节点4),进入节点4的调用逻辑 - 节点4不是
None,先执行lDepth = maxDepth(节点4.left),节点4的左是None,返回0 → 节点4的lDepth=0 - 节点4再执行
rDepth = maxDepth(节点4.right),节点4的右是None,返回0 → 节点4的rDepth=0 - 节点4取大值0加1,返回1 → 这个1就赋值给节点2的
lDepth - 节点2再执行
rDepth = maxDepth(节点5),节点5的左右都是None,最终返回1 → 节点2的rDepth=1 - 节点2取大值1加1,返回2 → 这个2就赋值给根节点1的
lDepth - 根节点1再执行
rDepth = maxDepth(节点3),节点3的左右都是None,最终返回1 → 根节点1的rDepth=1 - 根节点1取大值2加1,返回3 → 就是最终打印的树高度
整个过程是先自顶向下递归到最底层的叶子节点,再自底向上逐层返回计算好的子树深度,最终得到整棵树的最大深度。
内容的提问来源于stack exchange,提问作者Justin Yoon
相关产品推荐
相关产品推荐

