在二元树中找出和为某一值的所有路径
题目：输入一个整数和一棵二元树。从树的根结点开始往下访问一直到叶结点所经过的所有结点形成一条路径。打印出和与输入整数相等的所有路径。例如 输入整数22和如下二元树10/ /5 12/ /4 7则打印出两条路径：10, 12和10, 5, 7。二叉树节点的数据结构定义为：struct BinaryTreeNode // a node in the binary tree{int m_nValue; // value of nodeBinaryTreeNode *m_pLeft; // left child of nodeBinaryTreeNode *m_pRight; // right child of node};
访问到某一个节点时，将该节点的值加到当前值，并将该节点加到路径上，如果当前值等于所求值，判断当前节点是否叶节点，若是则输出路径，否则返回父节点；如果当前值小于所求值，则继续搜索孩子节点。如果当前值大于所求值，则返回父节点。返回父节点前记得将该节点从路径中删除，并把当前值减去该节点的值。
#include <iostream>
#include <vector>
using namespace std;
struct BinaryTreeNode
{
int m_nValue;
BinaryTreeNode *m_pLeft;
BinaryTreeNode *m_pRight;
}n1,n2,n3,n4,n5;
BinaryTreeNode* buildTree()
{
n1.m_nValue = 10;
n1.m_pLeft = &n2;
n1.m_pRight = &n3;
n2.m_nValue = 5;
n2.m_pLeft = &n4;
n2.m_pRight = &n5;
n3.m_nValue = 12;
n4.m_nValue = 4;
n5.m_nValue = 7;
n3.m_pLeft = n3.m_pRight = n4.m_pLeft = n4.m_pRight = n5.m_pLeft = n5.m_pRight = NULL;
return &n1;
}
void FindPath(BinaryTreeNode *pCurrent,int sum,int curval,vector<int> &path)
{
if(pCurrent == NULL)
{
return ;
}
curval += pCurrent->m_nValue;
path.push_back(pCurrent->m_nValue);
if(curval == sum)
{
if(pCurrent->m_pLeft == NULL && pCurrent->m_pRight == NULL)
{
for(vector<int>::iterator it = path.begin();it != path.end();it++)
{
cout<<*it<<" ";
}
cout<<endl;
}
}
else
{
if(pCurrent->m_pLeft)
{
FindPath(pCurrent->m_pLeft,sum,curval,path);
}
if(pCurrent->m_pRight)
{
FindPath(pCurrent->m_pRight,sum,curval,path);
}
}
curval -= pCurrent->m_nValue;
path.pop_back();
}
int main()
{
BinaryTreeNode *pRoot;
vector<int> path;
pRoot = buildTree();
FindPath(pRoot,22,0,path);
system("pause");
return 0;
}
评论 (0)
