在本章中，我们将看到如何打印从根节点到叶节点的所有路径。
问题陈述：
给您二叉树的根节点，您需要打印从根节点到叶节点的所有路径。
考虑下面的示例：
现在根据图像，我们有根节点“ a”和叶节点“ h”，“ e”，“ f”，“ g”。
因此，根据问题，您需要打印所有路径：
一种 -> b -> d -> h
一种 -> b -> e
一种 -> c -> f
一种 -> c -> g
现在我们来看看如何解决这个问题：
为了解决这个问题，我们将使用有序遍历和堆栈。
以下是执行顺序遍历的方法：
- 转到左侧子树直到null
- 打印根节点
- 转到右侧的子树
那么堆栈出现在哪里呢？
让我们借助示例来理解：
在上图中，如果在根节点上应用有序遍历，则遍历如下：
一种 -> b -> d -> h
现在，根据顺序遍历，您将打印h。但是根据问题，您需要打印完整路径。
那时堆栈将很有用。
如下图所示，堆栈如下所示：
现在，一旦到达叶子节点，我们将打印堆栈的全部内容。
但是我们什么时候应该从堆栈中弹出呢？
打印该节点时，我们将弹出顶部元素，然后转到该节点的父节点。
也就是说，一旦我们打印了节点“ h”，请转到其父节点“ d”。对于“ d”，没有合适的孩子。因此，我们回到“ b”。同时，我们删除“ h”和“ d”节点。
对于节点“ b”，有一个合适的孩子，我们将“ e”插入堆栈，如下所示：
现在，因为“ e”是叶节点，所以我们打印堆栈的内容
i.e 一种 -> b -> e
同样，我们访问了节点“ b”的所有子节点，因此我们从堆栈中删除了“ e”和“ b”。
现在我们到达根节点“ a”。节点“ A”的右子节点“ c”来自“ c”，我们转到“ f”并遵循相同的过程。
链接到此，我们将打印从根节点到叶节点的所有路径。
C ++解决方案
#include <iostream>
#include <stack>
#include <vector>
using namespace std;
// structure to hold binary tree node
struct Node
{
int data;
Node *left, *right;
Node(int data)
{
this->data = data;
this->left = this->right = nullptr;
}
};
void print_root_to_leaf_paths(Node* node, vector<int> &my_path)
{
if (node == NULL)
return;
my_path.push_back(node->data);
if (node->left == NULL && node->right == NULL)
{
for (int data: my_path)
cout << data << " ";
cout << endl;
}
print_root_to_leaf_paths(node->left, my_path);
print_root_to_leaf_paths(node->right, my_path);
my_path.pop_back();
}
int main()
{
Node* root = nullptr;
/* Binary tree:
16
/ \
/ \
10 25
/ \ / \
/ \ / \
7 15 18 30
*/
root = new Node(16);
root->left = new Node(10);
root->right = new Node(25);
root->left->left = new Node(7);
root->left->right = new Node(15);
root->right->left = new Node(18);
root->right->right = new Node(30);
vector<int> my_path;
print_root_to_leaf_paths(root, my_path);
return 0;
}
输出：
16 10 7 16 10 15 16 25 18 16 25 30
该网站上可用的教程列表：
| C编程20+章 | C ++编程80+章 |
| 100多个编码问题 | 数据结构和算法85+章 |
| 系统设计20+章 | Shell脚本编写12章 |
| 4g LTE 60+章节 | 最常见的编码问题 |
| 5G NR 50+章 | Linux系统编程20+章 |
