输出二叉树中从每个叶子结点到根结点的路径代码
时间: 2023-12-29 16:04:04 浏览: 27
好的,以下是输出二叉树中从每个叶子结点到根结点的路径代码:
```
void printPaths(Node* node) {
if (node == nullptr) return;
static vector<int> path;
path.push_back(node->val);
if (node->left == nullptr && node->right == nullptr) {
for (int val : path) {
cout << val << " ";
}
cout << endl;
} else {
printPaths(node->left);
printPaths(node->right);
}
path.pop_back();
}
```
该函数接受一个二叉树的根节点作为参数,并将输出二叉树中从每个叶子结点到根结点的路径。该函数采用递归的方式实现。从根节点开始,当遍历到某个叶子结点时,将该结点到根节点的路径输出,否则递归遍历左子树和右子树。由于要输出所有路径,因此需要保留路径上的结点值,使用一个静态向量 `path` 来存储当前路径。在递归返回的时候,需要将当前结点从 `path` 中弹出,以便处理其他路径。
相关问题
输出二叉树中从每个叶子结点到根结点的路径
以下是输出二叉树中从每个叶子结点到根结点的路径的 Python 代码:
```python
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def print_all_paths(root: TreeNode):
def dfs(node, path):
if not node:
return
path.append(node.val)
if not node.left and not node.right:
print(path[::-1])
else:
dfs(node.left, path)
dfs(node.right, path)
path.pop()
dfs(root, [])
```
这里我们使用深度优先搜索(DFS)遍历整个二叉树,并用一个列表 `path` 记录当前遍历路径上经过的结点值。当遇到叶子结点时,我们将 `path` 列表反转输出,即得到从叶子结点到根结点的路径。
注意在每次遍历完一个结点后,需要将其从 `path` 列表中弹出,以确保下一次遍历从正确的位置开始。
编程输出二叉树中从每个叶子结点到根结点的路径
以下是一个示例代码,实现了输出二叉树中从每个叶子结点到根结点的路径。假设二叉树的节点结构为TreeNode,包含左右子节点和节点值属性,可以使用递归方法来遍历二叉树并输出叶子结点到根结点的路径:
```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, path=[]):
# 如果节点为空,直接返回
if not root:
return
# 将当前节点值添加到路径列表中
path.append(root.val)
# 如果为叶子节点,输出路径
if not root.left and not root.right:
print(path[::-1])
# 递归遍历左子树
if root.left:
print_paths(root.left, path)
# 递归遍历右子树
if root.right:
print_paths(root.right, path)
# 弹出当前节点,回溯到上一层
path.pop()
# 测试代码
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_paths(root)
```
上述代码输出结果为:
```
[4, 2, 1]
[5, 2, 1]
[6, 3, 1]
[7, 3, 1]
```
其中每个列表表示从叶子节点到根节点的路径。