输出二叉树从每个叶子结点到根结点的路径
时间: 2023-06-05 07:47:20 浏览: 201
可以使用深度优先搜索(DFS)来输出二叉树从每个叶子结点到根结点的路径。具体步骤如下:
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
stack = []
dfs(root, stack)
def dfs(node, stack):
stack.append(node.val)
if not node.left and not node.right:
print(stack[::-1])
if node.left:
dfs(node.left, stack)
if node.right:
dfs(node.right, stack)
stack.pop()
```
其中,`print_paths`函数为入口函数,`dfs`函数为递归函数,`stack`为存储路径的栈。在`dfs`函数中,首先将当前节点加入栈中,然后判断当前节点是否为叶子节点,如果是,则输出栈中的所有节点,即为从该叶子节点到根节点的路径;否则,继续遍历其左右子树。遍历完当前节点的左右子树后,将该节点从栈中弹出,回溯到其父节点,继续遍历其兄弟节点。最终,输出所有叶子节点到根节点的路径。
阅读全文