采用先序遍历方法输出所有从叶子结点到根结点的逆路径
时间: 2023-12-29 20:04:36 浏览: 68
先序遍历是指先访问根节点,然后依次访问左子树和右子树。逆路径指的是从叶子节点到根节点的路径,因此我们需要在先序遍历中记录路径,并在遍历到叶子节点时输出路径的逆序。
下面是一个示例代码,假设二叉树的节点结构如下:
```python
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
```
我们可以定义一个递归函数来完成先序遍历和输出逆路径的过程:
```python
def print_reverse_paths(root, path=[]):
"""
输出从叶子节点到根节点的逆路径
:param root: 树根节点
:param path: 从根节点到当前节点的路径
"""
if not root:
return
# 先将当前节点加入路径中
path.append(root.val)
# 如果当前节点是叶子节点,输出逆路径
if not root.left and not root.right:
print(path[::-1])
# 递归遍历左子树和右子树
print_reverse_paths(root.left, path)
print_reverse_paths(root.right, path)
# 从路径中移除当前节点
path.pop()
```
我们可以使用以下代码来测试:
```python
# 创建一颗二叉树
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_reverse_paths(root)
```
输出结果为:
```
[4, 2, 1]
[5, 2, 1]
[6, 3, 1]
[7, 3, 1]
```
这里输出了从每个叶子节点到根节点的逆路径。
阅读全文