目录LeetCode 543. 二叉树的直径一、先理解题目要求二、那直径怎么计算三、那么 left_depth 和 right_depth 从哪里来四、递归函数到底应该返回什么五、那么直径在哪里计算六、完整代码为什么需要 nonlocal ans七、复杂度分析LeetCode 543. 二叉树的直径题目链接https://leetcode.cn/problems/diameter-of-binary-tree如果还没有看过二叉树递归的基础建议先看LeetCode 104. 二叉树的最大深度递归解法这道题和 104、110 的递归思路非常接近。104求每个节点向下的最大深度。110在求高度的过程中同时判断子树是否平衡。而 543在求高度的过程中利用左右子树高度计算当前节点作为最高点时的最大路径。另外弄了个网站可以看到代码执行过程中树的变化过程可视化一、先理解题目要求二叉树的直径是二叉树中任意两个节点之间最长路径的长度。( 注意, 最长路径不一定经过根节点。例如1 / \ 2 3 / 4最长路径4 - 2 - 1 - 3三条边, 所以直径 3所以我们需要找到整棵树中最长的一条路径。二、那直径怎么计算先不要考虑怎么解决, 咱先观察一下二叉树整体形状root / \ 左 右可以想想, 假设一条路径经过当前节点。那么为了让这条路径尽可能长它会尽量从左子树中选择最深的一条路再从右子树中选择最深的一条路。因此, 经过当前节点的最长路径其实就是左子树最大深度 右子树最大深度也就是left_depthright_depth因此对于任意一个节点我们都可以尝试如果最长路径经过我它的长度是多少然后取所有节点中的最大值。三、那么 left_depth 和 right_depth 从哪里来想到这里其实问题变成了 如何得到每个节点的left_depth right_depth这就和之前的 104 最大深度非常像。对于当前节点, 我们可以递归求left_depthfind_depth(node.left)right_depthfind_depth(node.right)然后计算left_depthright_depth看起来很简单。但是这里出现了一个不好想的问题递归函数到底应该返回什么四、递归函数到底应该返回什么想到这里很自然会产生一个想法既然当前节点计算直径时需要left_depth right_depth那么递归是不是应该直接返回(left_depth,right_depth)这样父节点拿到左右子树的信息后就可以继续计算。乍一看这个思路没有问题。但是再仔细思考后会发现递归函数返回的信息应该是提供给父节点继续使用的而不是单纯返回当前节点计算答案时需要的所有信息。假设0 | 1 / \ 2 3 / 4现在递归计算到了节点 1。它已经得到了left_depth2right_depth1因为左边最长路径1 - 2 - 4右边最长路径1 - 3所以节点 1 可以计算自己的直径候选值left_depthright_depth也就是2 1 3这个结果表示如果最长路径经过节点 1那么路径长度是多少。但是这个结果只属于节点 1。计算完成之后节点 1 还需要把信息返回给父节点 0。如果返回(left_depth,right_depth)也就是(2,1)那么节点 0 收到之后还需要重新判断自己继续向下延伸时应该选择哪一边。因为对于父节点来说它只能沿着一条路径继续向下。例如0 - 1 - 2 - 4或者0 - 1 - 3但是不能0 | 1 / \ 2 3同时连接左右两边。因为这已经是一条经过节点 1 的完整路径而不是继续向上的延伸。所以对于父节点来说它真正需要的信息不是(left_depth,right_depth)而是从当前节点出发向下最多还能延伸多长。因此递归函数应该返回max(left_depth,right_depth)1也就是选择左右子树中更长的一边继续提供给父节点使用。这里也解释了为什么最后返回的是高度而不是直径。很多人在写递归时容易默认函数最后 return 的东西就是题目要求的答案。但是在二叉树递归中情况并不一定如此。在这道题中 当前节点计算直径时需要left_depthright_depth因为它表示如果最长路径经过当前节点那么这条路径的长度是多少。但是这个结果只用于更新答案ansmax(ans,left_depthright_depth)并不适合作为递归返回值。因为递归返回值的作用是提供给父节点继续计算的信息。父节点真正需要知道的是通过当前节点向下最多还能延伸多少。所以返回max(left_depth,right_depth)1因此这道题中实际上有两个不同的计算当前节点计算答案时left_depthright_depth因为当前节点可以连接左右两边。返回给父节点时max(left_depth,right_depth)1因为父节点只能沿一条路径继续向下。这也是二叉树递归中非常重要的一点当前节点为了解决问题需要的信息不一定等于递归函数需要返回的信息。也就是说递归过程中return的内容不一定是最终答案它也可能是帮助上一层完成计算的中间信息。五、那么直径在哪里计算虽然递归返回的是max(left_depth,right_depth)1但是当前节点仍然拥有left_depth right_depth所以可以计算left_depthright_depth这就是如果最长路径经过当前节点它的长度。因此, 可以设计为每个节点都会计算一次自己的直径候选值递归到最底层 ↓ 返回左右子树高度 ↓ 当前节点计算left_depth right_depth ↓ 更新最大答案 ↓ 返回max(left_depth,right_depth)1 ↓ 继续向上六、完整代码classSolution:defdiameterOfBinaryTree(self,root:Optional[TreeNode])-int:ans0deffind_depth(node):nonlocalansifnodeisNone:return0left_depthfind_depth(node.left)right_depthfind_depth(node.right)# 当前节点作为最高点时的最长路径ansmax(ans,left_depthright_depth)# 返回当前节点能提供给父节点的信息returnmax(left_depth,right_depth)1find_depth(root)returnans为什么需要 nonlocal ans 首先思考一个问题为什么ans要定义在递归函数外面这是因为如果把它放在find_depth()内部deffind_depth(node):ans0那么每一次递归调用都会重新创建一个新的ans。find_depth(root) ↓ find_depth(left) ↓ find_depth(left.left)譬如在上面这个流程中每进入一层函数都会拥有自己的ans。这样的话不同节点计算出的路径长度无法共享也无法保存整棵树中的最大值。因此我们需要把ans0放在递归函数外层。这样所有递归调用都会共享同一个ans。每个节点计算出自己的路径长度后ansmax(ans,left_depthright_depth)都可以更新这个共同的答案。 但是Python 默认函数内部赋值会创建新的局部变量。所以在内部函数中直接修改外层变量ansmax(ans,left_depthright_depth)Python 会认为这里是在创建一个新的ans。因此需要nonlocalans告诉 Python我要修改外层函数中的ans而不是创建一个新的局部变量。七、复杂度分析每个节点只访问一次。对于每个节点计算左右子树高度更新答案返回高度。因此时间复杂度O(n)其中n是二叉树节点数量。递归调用栈最多保存从根节点到叶子节点的一条路径。因此空间复杂度O(h)其中h是二叉树高度。