二叉树应用_二叉树中和为某一值的路径

ゝ一纸荒年。 2022-05-22 03:00 157阅读 0赞

题目：输入一颗二叉树和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。从树的根节点往下一直到叶节点所经过的结点形成一条路径。  
分析：在二叉树的前序、中序、后序三种遍历方式中只有前序遍历先访问的是根节点。因此采用前序遍历的方式遍历树，当遍历到某一个节点时，我们把该结点添加到路径上，并且累加结点的值。并且，如果该结点为叶节点且累加的和刚好为输入的整数，则当前路劲符合要求，我们把它打印出来。如果当前节点不是叶节点，继续访问他的子节点。当当前节点访问完之后，要回到它的父节点，并且且路径和要回退成之前的。

struct TreeNode {
        int val;
        struct TreeNode *left;
        struct TreeNode *right;
        TreeNode(int x) :
                val(x), left(NULL), right(NULL) {
        }
    };*/
    
    //currentsum 采用传值而不是引用是因为，路劲的和在返回到父节点之前要回退成之前的。
    void findpath(TreeNode *root,vector<vector<int>>&result,vector<int>&path,int currentsum,int expectsum)
    {
        currentsum+=root->val;
        path.push_back(root->val);
        if(!root->left&&!root->right)
        {
            if(currentsum==expectsum)
                result.push_back(path);
            vector<int>::iterator it=path.begin();
            for(;it!=path.end();++it)
                cout<<*it<<" ";
            cout<<endl;
        }
        if(root->left)
            findpath(root->left,result,path,currentsum,expectsum);
        if(root->right)
            findpath(root->right,result,path,currentsum,expectsum);
        //返回到节点之前，在路径上删除当前节点
        path.pop_back();
    }
    
    vector<vector<int>> findpath(TreeNode*root,int expectsum)
    {
        vector<vector<int>> result;
        vector<int> path;
        int currentsum=0;
        if(root)
            findpath(root,result,path,currentsum,expectsum);
        return result;
    }