面试题25:二叉树中和为某一值的路径

题目:输入一颗二叉树和一个整数,打印出二叉树中节点值的和为输入整数的所有路径。从属的根节点开始往下一直到叶节点所经过的节点形成一条路径。二叉树节点的定义如下:

1
2
3
4
5
6
7
struct BinaryTreeNode{
int value;
BinaryTreeNode* left;
BinaryTreeNode* right;
BinaryTreeNode(int data=int()):value(data),left(NULL),right(NULL)
{}
};


分析

既然题目要求要打印二叉树上的所有节点,就需要遍历该二叉树。而在最常见的前、中、后序三种遍历方式中,只有前序遍历能第一个访问二叉树的根节点,也就是先累加根节点的值。所以可以在前序遍历的过程中计算当前路径上所以节点的和。如果当前节点是叶子节点且和等于给定的整数,就打印出当前路径上的节点。否则就将该叶子节点从路径上删除。由此可见,我们需要一个数组来保存当前的路径。

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
void _FindPath(BinaryTreeNode* root,int sum,vector<int>& v,int cursum)
{
if(root==NULL)
return;
cursum+=root->value;
v.push_back(root->value);
if(cursum==sum && root->left==NULL && root->right==NULL)
{
vector<int>::iterator iter=v.begin();
for(;iter!=v.end();++iter)
{
cout<<*iter<<" ";
}
cout<<endl;
}
else
{
_FindPath(root->left,sum,v,cursum);
_FindPath(root->right,sum,v,cursum);
}
v.pop_back();
return;
}
void FindPath(BinaryTreeNode* root,int sum)
{
vector<int> v;
_FindPath(root,sum,v,0);
}

以上

如果你有任何想法或是可以改进的地方,欢迎和我交流!

完整代码及测试用例在github上:点我前往

<div>来自为知笔记(Wiz)</div>