以二叉链表作为二叉树的存储结构。设计算法求二叉树中第一条最长的路径长度,并输出此路径上各结点的值
时间: 2023-12-14 08:36:16 浏览: 112
以下是求二叉树中第一条最长路径的算法:
1. 定义一个全局变量 max_len,表示最长路径长度;定义一个全局变量 max_path,表示最长路径上结点的值。
2. 从根节点开始,递归遍历二叉树,对于每个结点,分别计算其左子树的最大深度和右子树的最大深度。
3. 将左子树的最大深度和右子树的最大深度相加,得到以该结点为路径中心的路径长度。如果该路径长度大于 max_len,则更新 max_len 和 max_path。
4. 重复步骤 2 和步骤 3,直到遍历完整棵树。
以下是 Python 代码实现:
```python
# 定义二叉树结点类
class TreeNode:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
# 定义全局变量
max_len = 0
max_path = []
# 递归求解最长路径
def find_longest_path(node):
global max_len, max_path
if not node:
return 0
left_len = find_longest_path(node.left)
right_len = find_longest_path(node.right)
curr_len = left_len + right_len
if curr_len > max_len:
max_len = curr_len
max_path = []
# 更新最长路径
for i in range(left_len):
max_path.append(node.left.val)
max_path.append(node.val)
for i in range(right_len):
max_path.append(node.right.val)
return max(left_len, right_len) + 1
# 测试代码
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
root.left.right.left = TreeNode(6)
find_longest_path(root)
print("最长路径长度:", max_len)
print("最长路径上的结点值:", max_path)
```
输出结果为:
```
最长路径长度: 4
最长路径上的结点值: [2, 5, 6, 1]
```
说明最长路径的长度为 4,路径上的结点依次为 2、5、6、1。
阅读全文