求任意二叉树中一条最长的路径
时间: 2024-02-13 12:02:42 浏览: 15
在任意二叉树中,一条最长的路径一定是从该树的某个节点开始,经过该节点的左子树或右子树再到达该树的某个叶节点所形成的路径。因此,我们可以通过递归的方式来求解任意二叉树中一条最长的路径。
具体的,我们可以定义一个递归函数`dfs(node)`,该函数的作用是计算以节点`node`为根节点的子树中一条最长的路径的长度。在计算过程中,我们需要分别计算以`node.left`为根节点的子树中一条最长的路径的长度`left_height`和以`node.right`为根节点的子树中一条最长的路径的长度`right_height`,然后将这两个值加上`1`即可得到以`node`为根节点的子树的最长路径长度。
具体的实现可以参考下面的代码:
```python
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
def diameterOfBinaryTree(self, root: TreeNode) -> int:
self.ans = 0
def dfs(node):
if not node:
return 0
left_height = dfs(node.left)
right_height = dfs(node.right)
self.ans = max(self.ans, left_height + right_height)
return max(left_height, right_height) + 1
dfs(root)
return self.ans
```
在上面的代码中,我们定义了一个`ans`变量来记录整棵树中的最长路径长度。在递归函数`dfs(node)`中,如果节点`node`为空,则返回`0`;否则,我们分别计算以`node.left`和`node.right`为根节点的子树中的最长路径长度`left_height`和`right_height`,然后将这两个值相加得到以`node`为根节点的子树的最长路径长度,并更新`ans`变量。最后,我们将`dfs(root)`作为整个函数的返回值即可得到答案。
需要注意的是,在`dfs(node)`中,我们需要将以`node.left`和`node.right`为根节点的子树中最长路径长度的较大值加上`1`,而不是将它们直接相加。这是因为一条路径是从某个节点开始,经过该节点的左子树或右子树再到达某个叶节点,因此在计算以`node`为根节点的子树的最长路径长度时,我们只能选择`node.left`或`node.right`中较长的路径,而不能同时选择两个路径。