正文
careercup-树与图 4.9
提示：扫一扫查出行【扫一扫了解最新限行尾号】
复制提示
4.9 给定一颗二叉树，其中每个结点都含有一个数值。设计一个算法，打印结点数值总和等于某个给定值的所有路径。注意，路径不一定非得从二叉树的根节点或叶子节点开始或结束。
类似于leetcode：Path Sum II
C++实现代码：（使用了双重的递归）对于不含有parent指针域时。
#include<iostream>
#include<new>
#include<vector>
using namespace std; //Definition for binary tree
struct TreeNode
{
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
}; class Solution
{
public:
vector<vector<int> > path;
vector<vector<int> > pathSum(TreeNode *root, int sum)
{
vector<int> tmp;
hasPathSum(root,sum,tmp);
//改变开始的节点，不一定要从根结点开始，遍历从每一个节点开始
if(root->left)
pathSum(root->left,sum);
if(root->right)
pathSum(root->right,sum);
return path;
}
void hasPathSum(TreeNode *root, int sum,vector<int> tmp)
{
if(root==NULL)
return;
tmp.push_back(root->val);
//改变结束的地方，不一定要到叶子节点
if((sum-root->val)==)
{
path.push_back(tmp);
}
if(root->left)
hasPathSum(root->left,sum-root->val,tmp);
if(root->right)
hasPathSum(root->right,sum-root->val,tmp);
}
void createTree(TreeNode *&root)
{
int i;
cin>>i;
if(i!=)
{
root=new TreeNode(i);
if(root==NULL)
return;
createTree(root->left);
createTree(root->right);
}
}
};
int main()
{
Solution s;
TreeNode *root;
s.createTree(root);
vector<vector<int> > path=s.pathSum(root,);
for(auto a:path)
{
for(auto v:a)
cout<<v<<" ";
cout<<endl;
}
}
方法二：如果结点中包含指向父亲结点的指针，那么，只需要去遍历这棵二叉树， 然后从每个结点开始，不断地去累加上它父亲结点的值直到父亲结点为空(这个具有唯一性， 因为每个结点都只有一个父亲结点。也正因为这个唯一性， 可以不另外开额外的空间来保存路径)，如果等于给定的值sum，则打印输出。
实现的方法：
void find_sum(Node* head, int sum){
if(head == NULL) return;
Node *no = head;
int tmp = ;
for(int i=; no!=NULL; ++i){
tmp += no->key;
if(tmp == sum)
print(head, i);
no = no->parent;
}
find_sum(head->lchild, sum);
find_sum(head->rchild, sum);
}
打印输出时，只需要提供当前结点的指针，及累加的层数即可。然后从当前结点开始， 不断保存其父亲结点的值(包含当前结点)直到达到累加层数，然后逆序输出即可。
代码如下：
void print(Node* head, int level){
vector<int> v;
for(int i=; i<level; ++i){
v.push_back(head->key);
head = head->parent;
}
while(!v.empty()){
cout<<v.back()<<" ";
v.pop_back();
}
cout<<endl;
}
方法三：如果结点中不包含指向父亲结点的指针，则在二叉树从上向下查找路径的过程中， 需要为每一次的路径保存中间结果，累加求和仍然是从下至上的，对应到保存路径的数组， 即是从数组的后面开始累加的，这样能保证遍历到每一条路径。
代码如下：
void print2(vector<int> v, int level){
for(int i=level; i<v.size(); ++i)
cout<<v.at(i)<<" ";
cout<<endl;
}
void find_sum2(Node* head, int sum, vector<int> v, int level){
if(head == NULL) return;
v.push_back(head->key);
int tmp = ;
for(int i=level; i>-; --i){
tmp += v.at(i);
if(tmp == sum)
print2(v, i);
}
vector<int> v1(v), v2(v);
find_sum2(head->lchild, sum, v1, level+);
find_sum2(head->rchild, sum, v2, level+);
}
方法二 完整代码：
#include<iostream>
#include<new>
#include<map>
#include<vector>
using namespace std; struct BinarySearchTree
{
int elem;
BinarySearchTree *parent;
BinarySearchTree *left;
BinarySearchTree *right;
BinarySearchTree(int x):elem(x),parent(NULL),left(NULL),right(NULL) {}
}; void insert(BinarySearchTree *&root,int z)
{
BinarySearchTree *y=new BinarySearchTree(z);
if(root==NULL)
{
root=y;
return;
}
else if(root->left==NULL&&z<root->elem)
{
root->left=y;
y->parent=root;
return;
}
else if(root->right==NULL&&z>root->elem)
{
root->right=y;
y->parent=root;
return;
}
if(z<root->elem)
insert(root->left,z);
else
insert(root->right,z);
} void createBST(BinarySearchTree *&root)
{
int arr[]= {,,,,,,,,,};
for(auto a:arr)
insert(root,a);
} //使用level的原因就是因为，不一定要到根，只有根的父节点为NULL
void print(BinarySearchTree *head,int level)
{
vector<int> vec;
for(int i=;i<level;++i)
{
vec.push_back(head->elem);
head=head->parent;
}
while(!vec.empty())
{
cout<<vec.back()<<" ";
vec.pop_back();
}
cout<<endl;
}
//root选择的是当前结束的节点，也就是从下往上开始最下面的节点，而node是往上找到的刚好满足的最后一个结点，root是在不断加深的
void find_sum(BinarySearchTree *root,int sum)
{
if(root==NULL)
return;
BinarySearchTree *node=root;
int tmp=;
for(int i=;node!=NULL;++i)
{
tmp+=node->elem;
if(tmp==sum)
print(root,i);
node=node->parent;
}
find_sum(root->left,sum);
find_sum(root->right,sum);
}
int main()
{
BinarySearchTree *root=NULL;
createBST(root);
cout<<"find sum is: "<<endl;
find_sum(root,);
return ;
}
方法三 完整代码：
#include<iostream>
#include<new>
#include<map>
#include<vector>
using namespace std; struct BinarySearchTree
{
int elem;
BinarySearchTree *parent;
BinarySearchTree *left;
BinarySearchTree *right;
BinarySearchTree(int x):elem(x),parent(NULL),left(NULL),right(NULL) {}
}; void insert(BinarySearchTree *&root,int z)
{
BinarySearchTree *y=new BinarySearchTree(z);
if(root==NULL)
{
root=y;
return;
}
else if(root->left==NULL&&z<root->elem)
{
root->left=y;
y->parent=root;
return;
}
else if(root->right==NULL&&z>root->elem)
{
root->right=y;
y->parent=root;
return;
}
if(z<root->elem)
insert(root->left,z);
else
insert(root->right,z);
} void createBST(BinarySearchTree *&root)
{
int arr[]= {,,,,,,,,,};
for(auto a:arr)
insert(root,a);
} //使用level记录选择v中的从哪个下标开始相加
void print(vector<int> v,int level)
{
for(int i=level;i<v.size();++i)
cout<<v[i]<<" ";
cout<<endl;
}
//root开始，将当前层的值加入v中
void find_sum(BinarySearchTree *root,int sum,vector<int> v,int level)
{
if(root==NULL)
return;
v.push_back(root->elem);
int tmp=;
for(int i=level;i>-;--i)
{
tmp+=v[i];
if(tmp==sum)
print(v,i);
}
//每一层将当前层的结点的值放入v中，由于不是传递的引用，所以同一层放入v中的值不会影响，从root结点开始保存每一层的
find_sum(root->left,sum,v,level+);
find_sum(root->right,sum,v,level+);
}
int main()
{
BinarySearchTree *root=NULL;
createBST(root);
vector<int> v;
cout<<"find sum is: "<<endl;
find_sum(root,,v,);
return ;
}
