6. 输出二叉树从每个叶子结点到根结点的路径(经历的结点)
时间: 2023-12-29 08:05:13 浏览: 63
数据结构大作业求二叉树上结点的路径.zip
5星 · 资源好评率100%
可以使用递归来输出二叉树从每个叶子结点到根结点的路径。
具体实现步骤如下:
1. 定义一个递归函数,该函数接收两个参数:当前遍历到的节点和一个字符串,表示当前节点之前经历的路径。
2. 如果当前节点为空,则直接返回。
3. 如果当前节点为叶子节点,说明已经遍历到了路径的末尾,此时将经历的路径字符串和当前节点的值拼接起来,输出即可。
4. 如果当前节点不是叶子节点,则将当前节点的值和一个箭头符号拼接到经历的路径字符串中,然后分别递归遍历左右子树,将左右子树的结果合并起来。
5. 最终得到的结果就是从当前叶子节点到根节点的完整路径。
以下是示例代码实现:
```python
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def print_paths(root):
if not root:
return []
paths = []
def dfs(node, path_str):
if not node:
return
if not node.left and not node.right:
paths.append(path_str + str(node.val))
return
dfs(node.left, path_str + str(node.val) + "->")
dfs(node.right, path_str + str(node.val) + "->")
dfs(root, "")
return paths
# 示例
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(print_paths(root)) # ['1->2->4', '1->2->5', '1->3->6', '1->3->7']
```
输出结果为:`['1->2->4', '1->2->5', '1->3->6', '1->3->7']`,表示从每个叶子节点到根节点的路径。
阅读全文