九章算法 | 海康威视面试题：路径总和 II

描述

给定一个二叉树和一个目标和，找到所有从根节点到叶子节点路径总和等于给定目标和的路径。

叶子节点是指没有子节点的节点。

在线评测地址

LintCode 领扣

样例1

输入: root = {5,4,8,11,#,13,4,7,2,#,#,5,1}, sum = 22 
              5 
             / \ 
            4   8 
           /   / \ 
          11  13  4 
         /  \    / \ 
        7    2  5   1 
输出: [[5,4,11,2],[5,8,4,5]] 
解释: 
两条路径之和为 22： 
5 + 4 + 11 + 2 = 22 
5 + 8 + 4 + 5 = 22 

样例2

输入: root = {10,6,7,5,2,1,8,#,9}, sum = 18 
              10 
             /  \ 
            6    7 
          /  \   / \ 
          5  2   1  8 
           \  
            9  
输出: [[10,6,2],[10,7,1]] 
解释: 
两条路径之和为 18： 
10 + 6 + 2 = 18 
10 + 7 + 1 = 18 

当访问的节点是叶子节点的时候，新建一个列表，插入到result中，然后返回result。 分别遍历左右子树的节点，然后将他们分别插入到叶子节点之前。

/** 
 * Definition of TreeNode: 
 * class TreeNode { 
 * public: 
 *     int val; 
 *     TreeNode *left, *right; 
 *     TreeNode(int val) { 
 *         this->val = val; 
 *         this->left = this->right = NULL; 
 *     } 
 * } 
 */ 
 
class Solution { 
public: 
    /** 
     * @param root: a binary tree 
     * @param sum: the sum 
     * @return: the scheme 
     */ 
    vector<vector<int>> pathSum(TreeNode * root, int sum) { 
        // Write your code here. 
        vector<int> path; 
        vector<vector<int>> Spath; 
        int weight = 0; 
        findpath(Spath,root,sum,path,weight); 
        return Spath; 
    } 
    void findpath(vector<vector<int>> &Spath,TreeNode* root,int sum,vector<int> &path,int weight) 
    { 
 
        if(root == NULL){ 
            return; 
        } 
        weight = weight + root->val; 
        path.push_back(root->val); 
        if(weight == sum && root->left == NULL && root->right == NULL) 
        { 
            Spath.push_back(path); 
            weight = weight - root->val; 
            path.pop_back(); 
            return; 
        } 
        findpath(Spath,root->left,sum,path,weight); 
        findpath(Spath,root->right,sum,path,weight); 
        path.pop_back();  
    } 
}; 
 

更多题解参考：九章算法