在二叉树中查找和为某一值的所有路径

在二叉树中，我们求根节点到叶子节点和为某一数值的路径，并打印出来。
如下图所示：
我们求解和为16的路径，那么我们可以求解出两条路径，一条为5-4-7，一条为5-8-3。那么在处理二叉树的时候我们会用递归的算法。由于涉及到存储路径，我们可以用堆栈的思想，并且在进行下一步计算之前，对现场进行恢复。整体的实现代码如下所示：
#include
#include
using namespace std;
typedef struct node
{
int val;
node *lChild;
node *rChild;
node(int val)
{
this->val = val;
this->lChild = nullptr;
this->rChild = nullptr;
}
node()
{
this->lChild = nullptr;
this->rChild = nullptr;
}
}TreeNode;
TreeNode *createtree(int i, int intarr[], int length)//根据数组创建二叉树
{
TreeNode *node = nullptr;
if (i == 0)
{
node = new TreeNode(intarr[i]);
node->lChild = createtree(i * 2 + 1, intarr, length);
node->rChild = createtree(i * 2 + 2, intarr, length);
}
else if (i < length)
{
node = new TreeNode(intarr[i]);
node->lChild = createtree(i * 2 + 1, intarr, length);
node->rChild = createtree(i * 2 + 2, intarr, length);
}
return node;
}
void display(vector path)//打印存储路径
{
for (auto x : path)
{
cout << x << " ";
}
cout << endl;
}
bool isLeaf(TreeNode *node)//判断是否为叶子节点
{
return (!node->lChild) && (!node->rChild);
}
void findPath(TreeNode *node, int expext, int &cursum, vector &path)
//node是需要计算的节点，expext是期望值，cursum是当前的值，path是存储的路径
{
if (node==nullptr)
{
return;
}
if (cursum+node->val == expext && isLeaf(node))//当且仅当cursum和node->val和为expext，且node为叶子节点的时候，执行打印路径操作。
{
path.push_back(node->val);
display(path);
path.pop_back();//执行完打印路径的操作，需要把node节点pop出来，一遍进行下一次计算的时候不出错。
return;
}
else
{
cursum = cursum + node->val;//上述条件不满足的时候，把node->val加到cursum中，并且把node push到path里面。对其两个节点进行计算。
path.push_back(node->val);
if (node->lChild)
{
findPath(node->lChild, expext, cursum, path);//计算左节点是否满足条件。
}
if (node->rChild)
{
findPath(node->rChild, expext, cursum, path);//计算右节点是否满足条件。
}
cursum = cursum - node->val;//以下两个步骤都是恢复现场，以便进行下一个节点计算的时候，不会出错。
path.pop_back();
return;
}
}
int main()
{
int intarr[6] = { 5,4,8,7,1,3 };
TreeNode *root = createtree(0, intarr, 6);
int cursum = 0;
int expectsum = 16;
vector path;
findPath(root, expectsum, cursum, path);
system(“pause”);
return 0;
}
执行结果：

在本算法中使用了回溯的思想，回溯的思想的最主要的就是要保存现场和恢复现场，以便进行下一次计算的时候不会把当前的计算结果杂糅到下一次的计算结果中，导致计算结果不正确。

在二叉树中查找和为某一值的所有路径

相关推荐