leetcode || 113、Path Sum II

problem：

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

Hide Tags   Tree Depth-first Search 题意：在二叉树根节点到叶子节点的所有路径上，如果路径节点数值之和为特定数sum，输出所有满足该条件的路径

thinking：

是上道题的变形，DFS遍历所有孩子节点，并记录路径和。到达叶子节点时（左右孩子为空）判断是否为有效路径，有效则保存该路径。

code：

class Solution {
  private:
      vector<vector<int> > ret;
  public:
      vector<vector<int> > pathSum(TreeNode *root, int sum) {
          ret.clear();
          vector<int> path;
          if(root==NULL)
              return ret;
          dfs(0,sum,path,root);
          return ret;
      }
  protected:
      void dfs(int add, int sum, vector<int> path,TreeNode *node)
      {
          path.push_back(node->val);
          add+=node->val;
          if(node->left==NULL && node->right==NULL)
          {
              if(add==sum)
                  ret.push_back(path);
              return;
          }
          if(node->left!=NULL)
              dfs(add,sum,path,node->left);
          if(node->right!=NULL)
              dfs(add,sum,path,node->right);
      }
  };