[Leetcode] Path Sum II路径和

Given a binary tree and a sum, find all root-to-leaf paths where each path's sum equals the given sum.

For example:
Given the below binary tree andsum = 22,

              5

             / \

            4   8

           /   / \

          11  13  4

         /  \    / \

        7    2  5   1

return

[

   [5,4,11,2],

   [5,8,4,5]

]

题意：给定一数，在树中找出所有路径和等于该数的情况。
方法一：
使用vector向量实现stack的功能，以方便输出指定路径。思想和代码和Path sum大致相同。

/**

 * Definition for binary tree

 * struct TreeNode {

 *     int val;

 *     TreeNode *left;

 *     TreeNode *right;

 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}

 * };

 */

class Solution {

public:

    vector<vector<int> > pathSum(TreeNode *root, int sum)

    {

        vector<vector<int>> res;

        vector<TreeNode *> vec;

        TreeNode *pre=NULL;

        TreeNode *cur=root;

        int temVal=;

        while(cur|| !vec.empty())

        {

            while(cur)

            {

                vec.push_back(cur);

                temVal+=cur->val;

                cur=cur->left;

            }

            cur=vec.back();

            if(cur->left==NULL&&cur->right==NULL&&temVal==sum)

            {       //和Path sum最大的区别

                vector<int> temp;

                for(int i=;i<vec.size();++i)

                    temp.push_back(vec[i]->val);

                res.push_back(temp);

            }

            if(cur->right&&cur->right !=pre)

                cur=cur->right;

            else

            {

                vec.pop_back();

                temVal-=cur->val;

                pre=cur;

                cur=NULL;

            }

        }

        return res;

    }

};

方法二：递归法

/**

 * Definition for binary tree

 * struct TreeNode {

 *     int val;

 *     TreeNode *left;

 *     TreeNode *right;

 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}

 * };

 */

class Solution {

public:

    vector<vector<int> > pathSum(TreeNode *root, int sum)

    {

        vector<vector<int>> res;

        vector<int> path;

        findPaths(root,sum,res,path);

        return res;

    }

    void findPaths(TreeNode *root,int sum,vector<vector<int>> &res,vector<int> &path)

    {

        if(root==NULL)  return;

        path.push_back(root->val);

        if(root->left==NULL&&root->right==NULL&&sum==root->val)

            res.push_back(path);

        findPaths(root->left,sum-root->val,res,path);

        findPaths(root->right,sum-root->val,res,path);

        path.pop_back();

    }

};

巴特西

[Leetcode] Path Sum II路径和

最新文章

热门文章