二叉树输出最长路径上的结点
时间: 2023-12-27 11:03:40 浏览: 38
首先,我们需要知道什么是二叉树的路径。二叉树的路径是指从树的根结点到任意结点的经过的结点序列。而最长路径则是指从树的根结点到叶子结点路径中包含结点数最多的那条路径。
要输出最长路径上的结点,可以考虑使用深度优先搜索(DFS)来遍历整棵树,记录下每个结点到根结点的路径长度和路径上的结点。在遍历的过程中,如果当前结点是叶子结点,那么就判断它到根结点的路径长度是否是当前遍历到的最长路径。如果是,则更新最长路径和最长路径上的结点。
以下是示例代码:
```
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
def __init__(self):
self.max_len = 0 # 最长路径长度
self.max_path = [] # 最长路径上的结点序列
def find_longest_path(self, root):
self.dfs(root, [root.val])
return self.max_path
def dfs(self, node, path):
if not node.left and not node.right: # 叶子结点
if len(path) > self.max_len:
self.max_len = len(path)
self.max_path = path
if node.left:
self.dfs(node.left, path + [node.left.val])
if node.right:
self.dfs(node.right, path + [node.right.val])
```
在这个示例代码中,我们定义了一个 `TreeNode` 类来表示二叉树的结点。`Solution` 类中的 `find_longest_path` 方法是我们的主要方法,它接受二叉树的根结点作为参数,并返回最长路径上的结点序列。
在 `dfs` 方法中,我们首先判断当前结点是否是叶子结点。如果是,就判断当前路径的长度是否大于当前的最长路径长度。如果是,则更新最长路径长度和最长路径上的结点序列。
接下来,我们分别遍历当前结点的左子树和右子树,如果存在的话。在遍历左子树和右子树的过程中,我们需要将当前结点的值添加到路径中,并继续遍历子树。
最后,我们可以调用 `find_longest_path` 方法来获取最长路径上的结点序列。