打印二进制树中所有的根到叶路径:错误的输出

Question

我正在努力解决这个问题：

给定一个二叉树，打印所有从根到叶的路径。

我想我已经理解了需要实现的逻辑，但我的代码没有给出所需的输出。

示例

对于此树：

1
/   
2     3
/    / 
4   5 6   7

预期输出为：

1 2 4
1 2 5
1 3 6
1 3 7

但我的代码输出的是：

4
2 5
1 6
1 3 7

代码

下面是我的C++代码：

#include <iostream>
#include <queue>
#include <vector>
using namespace std;
struct node {
int data;
struct node* left;
struct node* right;
};
vector <int> ans;
struct node* newnode(int data)
{
struct node* temp=(struct node*)malloc(sizeof(struct node));
temp->data=data;
temp->left=NULL;
temp->right=NULL;
return temp;
}
void root_to_leaf_path(struct node* root)
{
if(root==NULL)
return;
root_to_leaf_path(root->left);
ans.push_back(root->data);
if(root->left==NULL && root->right==NULL)
{
int n=ans.size();
for(int i=0;i<n;i++)
{
cout<<ans[i]<<" ";
}
cout<<endl;
}
root_to_leaf_path(root->right);
ans.pop_back();
}
int main()
{
struct node* root=newnode(1);
struct node* p1=newnode(2);
struct node* p2=newnode(3);
struct node* p3=newnode(4);
struct node* p4=newnode(5);
struct node* p5=newnode(6);
struct node* p6=newnode(7);
root->left=p1;
root->right=p2;
p1->left=p3;
p1->right=p4;
p2->left=p5;
p2->right=p6;
root_to_leaf_path(root);
}

错误在哪里？

Answer 1

从您得到的输出中可以看出，根不是首先输出的。之所以会发生这种情况，是因为代码首先进行递归调用，然后才将值推送到向量。这意味着最深的值将首先被推送。

在进行递归调用之前，您应该将值推送到向量：这样，当您沿着树往下走时，值就会累积。

所以改变这个：

root_to_leaf_path(root->left);
ans.push_back(root->data);

到此：

ans.push_back(root->data);
root_to_leaf_path(root->left);