[LeetCode] Path Sum II - c++编程基础

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,

/ \

4 8

/ / \

11 13 4

/ \ / \

7 2 5 1

return

[

[5,4,11,2],

[5,8,4,5]

]

问题描述：给定一个二叉树和一个数，找到在这个二叉树中从根节点到叶子节点路径和等于这个数字的所有路径。

前面多次提到，与二叉树相关的问题，多半都可以用递归。

对于本题而言，vector > pathSum(TreeNode *root, int sum)函数返回以root为根的路径和等于sum的所有路径，那么可以这么想

pathSum(root->left, sum-(root->val))返回左子树中和为sum-(root->val)的所有路径，

pathSum(root->right, sum-(root->val))返回右子树中和为sum-(root->val)的所有路径，

那么pathSum(root, sum)可以通过将root->val加入到上面所有路径中，然后将左右子树的路径进行合并得到。

然后再判断临界条件即可。







class Solution {  
public:  
    vector > pathSum(TreeNode *root, int sum) {  
        // IMPORTANT: Please reset any member data you declared, as  
        // the same Solution instance will be reused for each test case.  
        if(root == NULL)  
            return vector >();  
          
        if(root->left == NULL && root->right == NULL && root->val == sum) {  
            vector > vec;  
            vector ivec;  
            ivec.push_back(sum);  
            vec.push_back(ivec);  
            return vec;  
        }  
          
        vector > vec1 = pathSum(root->left, sum-(root->val));  
        vector > vec2 = pathSum(root->right, sum-(root->val));  
        for(vector >::iterator iter = vec1.begin();  
                                           iter != vec1.end(); ++iter) {  
            (*iter).insert((*iter).begin(), root->val);  
        }  
          
        for(vector >::iterator iter = vec2.begin();  
                                           iter != vec2.end(); ++iter) {  
            (*iter).insert((*iter).begin(), root->val);  
            vec1.push_back(*iter);  
        }  
          
        return vec1;  
    }  
};