编写算法求给定二叉树中一条最长的路径,并输出此路径上各结点的值。
时间: 2023-03-22 13:04:41 浏览: 243
求二叉树上结点的路径 代码 及说明
5星 · 资源好评率100%
要求给定一棵二叉树,编写算法求出其中一条最长的路径,并输出此路径上各结点的值。
算法思路:
1. 首先,我们需要遍历整棵二叉树,找到所有的叶子节点。
2. 对于每个叶子节点,我们需要计算它到根节点的路径长度。
3. 对于每个节点,我们需要计算它的左子树和右子树中最长的路径长度。
4. 最后,我们需要比较所有路径长度,找到其中最长的一条路径,并输出此路径上各结点的值。
算法实现:
1. 遍历整棵二叉树,找到所有的叶子节点。
2. 对于每个叶子节点,计算它到根节点的路径长度。
3. 对于每个节点,计算它的左子树和右子树中最长的路径长度。
4. 比较所有路径长度,找到其中最长的一条路径,并输出此路径上各结点的值。
代码实现:
```
class TreeNode:
def __init__(self, val=, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
def __init__(self):
self.max_path = []
self.max_len =
def find_longest_path(self, root):
if not root:
return
left_len = self.find_longest_path(root.left)
right_len = self.find_longest_path(root.right)
if left_len + right_len > self.max_len:
self.max_len = left_len + right_len
self.max_path = [root.val] + self.max_path
return max(left_len, right_len) + 1
def longestPath(self, root: TreeNode) -> List[int]:
self.find_longest_path(root)
return self.max_path
```
以上是一个 Python 实现的算法,其中 `TreeNode` 表示二叉树节点的类,`Solution` 表示算法的实现类。
在 `find_longest_path` 方法中,我们使用递归的方式计算每个节点的左子树和右子树中最长的路径长度,并比较它们的和是否大于当前最长路径长度。如果是,则更新最长路径长度和最长路径。
在 `longestPath` 方法中,我们调用 `find_longest_path` 方法来计算最长路径,并返回最长路径。
阅读全文