设计算法,输出二叉树中从每个叶子结点到根结点的路径
时间: 2024-05-09 10:04:48 浏览: 16
可以使用深度优先搜索(DFS)来遍历二叉树,并且在每个叶子节点处记录路径。具体步骤如下:
1. 定义一个栈,用于存储结点,将根结点入栈。
2. 定义一个哈希表用于存储每个叶子节点的路径,初始为空。
3. 当栈不为空时,取出栈顶结点。
4. 如果该结点是叶子节点,则记录该结点路径(从该叶子节点到根节点的路径为从哈希表中该叶子节点的路径倒序连接上该叶子节点的值和"/")。
5. 否则,将该结点的右子节点和左子节点分别入栈。
6. 重复步骤3-5直至栈为空。
最后,输出哈希表中记录的所有路径即可。
相关问题
输出二叉树中从每个叶子结点到根结点的路径代码
好的,以下是输出二叉树中从每个叶子结点到根结点的路径代码:
```
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` 列表中弹出,以确保下一次遍历从正确的位置开始。