【面试题】剑指offer25--二叉树中和为某一值的路径

时间:2022-11-25 20:37:50

输入一颗二叉树和一整数,打印出二叉树中节点值的和为输入整数的所有路径。

从树的根节点开始往下一直到叶节点经过的结点形成一条路径。

例如:输入的二叉树如下图所示,输入的整数位22

【面试题】剑指offer25--二叉树中和为某一值的路径

由图可以知道,路径为22 的路径有两条。

第一条是包含节点10,12;

第二条路径包含节点10,5,7;

访问这颗二叉树的过程如下:

【面试题】剑指offer25--二叉树中和为某一值的路径

代码实现:

#include<iostream>
using namespace std;
#include<vector>
struct BinaryTreeNode
{
int _value;
BinaryTreeNode* _left;
BinaryTreeNode* _right;

};

void FindPath(BinaryTreeNode* root, int exp)
{
if (root == NULL)
{
return;
}
std::vector<int> path;
int curr = 0;
FindPath(root, exp, path, curr);
}

void FindPath(BinaryTreeNode* root, int exp, std::vector<int>& path, int& curr)
{
curr += root->_value;
path.push_back(root->_value);

bool isLeaf = root->_left == NULL&&root->_right == NULL;
if (curr == exp&&isLeaf)
{
printf("A path is found: ");
std::vector<int>::iterator iter = path.begin();
for (; iter != path.end(); ++iter)
{
printf("%d\t", *iter);
}
printf("\n");
}
if (root->_left != NULL)
{
FindPath(root->_left, exp, path, curr);
}
if (root->_right != NULL)
{
FindPath(root->_right, exp, path, curr);
}
curr -= root->_value; path.pop_back();
}