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);
      }
  };