首页 > 其他 > 详细

Leetcode Path Sum II

时间:2014-07-02 22:10:22      阅读:466      评论:0      收藏:0      [点我收藏+]

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 and sum = 22,
              5
             /             4   8
           /   /           11  13  4
         /  \    /         7    2  5   1

return

[
   [5,4,11,2],
   [5,8,4,5]
]
递归实现,注意递归实现时,放入vector中的数据,之后要pop_back出,此题中path参数没有使用引用,是按值传递的
bubuko.com,布布扣
class Solution {
public:
    vector<vector<int> > res;
    
    void solvePathSum(TreeNode *root, int sum, vector<int> path){
        if(root == NULL) return;
        if(root->left == NULL && root->right == NULL){
            if(sum == root->val){
                path.push_back(root->val);
                res.push_back(path);
            }
            return;
        }
        path.push_back(root->val);
        solvePathSum(root->left,sum-root->val,path);
        solvePathSum(root->right,sum-root->val,path);
    }

    vector<vector<int> > pathSum(TreeNode *root, int sum) {
        vector<int> path;
        solvePathSum(root,sum,path);
        return res;
    }
};
递归实现

 非递归实现,在节点中添加了一个指向父节点的指针

class Solution {
public:
    struct TreeNodeSum{
        TreeNode *node;
        TreeNodeSum *parent;
        int sum;
        TreeNodeSum(TreeNode* node_, int sum_, TreeNodeSum* parent_ = NULL ):node(node_),sum(sum_),parent(parent_){}
    };
    
    vector<vector<int> > pathSum(TreeNode *root, int sum) {
        vector<vector<int> >res;
        if(root == NULL) return res;
        queue<TreeNodeSum *> que;
        que.push(new TreeNodeSum(root,root->val));
        while(!que.empty()){
            TreeNodeSum *tmp = que.front();que.pop();
            TreeNode *node = tmp->node;
            if(!node->left && !node->right && tmp->sum == sum){
                vector<int> path;
                while(tmp){
                    path.push_back(tmp->node->val);
                    tmp = tmp->parent;
                }
                reverse(path.begin(),path.end());
                res.push_back(path);
                continue;
            }
            if(node->left){
                TreeNodeSum *nodeSum = new TreeNodeSum(node->left,node->left->val+tmp->sum,tmp);
                que.push(nodeSum);
            }
            if(node->right ){
                TreeNodeSum *nodeSum = new TreeNodeSum(node->right,node->right->val+tmp->sum,tmp);
                que.push(nodeSum);
            }
        }
        return res;
    }
}; 

Leetcode Path Sum II,布布扣,bubuko.com

Leetcode Path Sum II

原文:http://www.cnblogs.com/xiongqiangcs/p/3818983.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!