对给定的二叉树,缤写一个程序,输出从叶子结点到根结点的最左边的一条最长路径。
时间: 2024-04-29 09:23:49 浏览: 113
我们可以使用深度优先搜索(DFS)来解决这个问题。从根节点开始,对于每个叶子节点,记录从根节点到该叶子节点的路径,并比较该路径的长度和最长路径的长度。如果该路径的长度大于最长路径的长度,则更新最长路径。
具体实现步骤如下:
1. 定义一个全局变量 maxLen,表示最长路径的长度,一个全局变量 maxPath,表示最长路径。
2. 定义一个 DFS 函数,接受当前节点 node 和当前路径 path 作为参数。
3. 如果 node 是叶子节点,计算 path 的长度,并与 maxLen 比较,如果 path 的长度大于 maxLen,则更新 maxLen 和 maxPath。
4. 如果 node 不是叶子节点,递归遍历 node 的左子树和右子树,分别传入更新后的 path。
5. 在主函数中调用 DFS(root, []),其中 root 是二叉树的根节点,[] 表示初始路径为空。
6. 输出 maxPath。
代码如下:
```python
class TreeNode:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
maxLen = 0
maxPath = []
def DFS(node, path):
global maxLen, maxPath
if not node.left and not node.right: # node is leaf node
path.append(node.val)
if len(path) > maxLen:
maxLen = len(path)
maxPath = path[:]
path.pop()
else:
path.append(node.val)
if node.left:
DFS(node.left, path)
if node.right:
DFS(node.right, path)
path.pop()
def longest_path(root):
global maxLen, maxPath
DFS(root, [])
return maxPath[::-1]
# test
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
root.right.left = TreeNode(6)
root.right.right = TreeNode(7)
print(longest_path(root)) # [4, 2, 1]
```
阅读全文