频道栏目
首页 > 考试 > 其他 > 正文

leetcode No113. Path Sum II

2016-08-26 09:35:33         来源:wc19930807的博客  
收藏   我要投稿

Question:

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]
]

 

求路径和等于sum的路径

Algorithm:

DFS

Accepted Code:

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector> pathSum(TreeNode* root, int sum) {
        vector> res;
        vector temp;
        help(root,res,temp,sum);
        return res;
    }
    void help(TreeNode* root,vector> &res,vector v,int sum)
    {
        if(root==NULL)
            return;
        v.push_back(root->val);
        if(root->left==NULL&&root->right==NULL&&root->val==sum)
        {
            res.push_back(v);
            return;
        }
        else if(root->left==NULL&&root->right==NULL)    
            return;
        else
        {
            if(root->left)
                help(root->left,res,v,sum-root->val);
            if(root->right)
                help(root->right,res,v,sum-root->val);
        }
    }
};


相关TAG标签
上一篇:LeetCode 37 Sudoku Solver
下一篇:剑指-旋转数组的最小数
相关文章
图文推荐

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站