首页 > 代码库 > 二叉树中存在路径等于给定值

二叉树中存在路径等于给定值

2024-07-08 11:49:03   225人阅读

题目：输入一个二叉树和一个整数，打印出二叉树中所有和给定整数值相等的路径。

分析：先画图

image

明白几点：

1）根据题意，我们是要遍历整个树才能确定所有符合条件的路径。显然应该从根节点出发，那么我们就应该采用先序遍历。这里遍历就采用递归更简单。

2）遍历完了后如何保存路径呢？这里我们是采用vector而不是stack因为遍历的时候从根节点打印。

    每次遍历一个结点，就将其压栈，当前结点访问结束后，递归函数将自动回到父节点，因此我们在函数退出之前要在路径上删除当前结点并减去当前结点的值。

#include <iostream>#include <vector>   //用vector而不用stack是因为vector便于从根节点开始打印using namespace std;struct BinaryTreeNode{    int m_rootData;    BinaryTreeNode* m_leftChildren;    BinaryTreeNode* m_rightChildren;};void createTree(BinaryTreeNode *&Node){    int ch;    cin >> ch;    if (ch == 100)                               //有木有更好的方法        Node = NULL;                          //注意，当输入为100时候 结点为NULL，刚开始一直检查不出错误。    else    {        Node = new BinaryTreeNode;        if (!Node)            return;        Node->m_rootData =http://www.mamicode.com/ch;         //将字符转化为int        createTree(Node->m_leftChildren);        createTree(Node->m_rightChildren);    }}void FindPath(BinaryTreeNode*pNode, int value, int currentValue, vector<int>Vector);void FindPath(BinaryTreeNode* pNode,int value){    //1.容错性判断    if (pNode == NULL || value =http://www.mamicode.com/= 0)        return;    //2.定义一个vector，vector是用来保存经过的路径，作用仅仅只是为了输出符合要求的路径    vector<int> pathVector;    int current_value =http://www.mamicode.com/ value;    //3.递归只是用来先序遍历树的所有结点    FindPath(pNode, value, current_value, pathVector);}void FindPath(BinaryTreeNode*pNode, int value, int currentValue,vector<int>Vector){    Vector.push_back(pNode->m_rootData);    currentValue  -= pNode->m_rootData;      //先序遍历，先根节点，下面的递归是左右子树    if (currentValue =http://www.mamicode.com/= 0 && pNode->m_leftChildren == NULL&&pNode->m_rightChildren == NULL)//满足要求的路径条件    {        cout << "找到了：" << endl;        for (vector<int>::iterator it = Vector.begin(); it != Vector.end(); ++it)            cout << *it << "  ";           cout << endl;    }    //下面的递归主要是为了遍历树结点，这里要和树非递归先序遍历别弄混了，树的非递归时要用到栈的。    if (pNode->m_leftChildren)        FindPath(pNode->m_leftChildren, value, currentValue,Vector);    if (pNode->m_rightChildren)        FindPath(pNode->m_rightChildren, value, currentValue,Vector);    Vector.pop_back();      //要理解递归的过程，每个结点的值都会保存下来。函数退出的时候要删除当前结点的值}  int _tmain(int argc, _TCHAR* argv[]){    BinaryTreeNode* BinTree;    createTree(BinTree);                   FindPath(BinTree, 22);    return 0;}

结果：

image


联系
我们