Leetcode 129: sum roof to leaf numbers/Leetcode 112: path sum/Leetcode 113: pathsumII

Given a binary tree containing digits from 0-9 only, each root-to-leaf path could represent a number.
An example is the root-to-leaf path 1->2->3 which represents the number 123.
Find the total sum of all root-to-leaf numbers.
For example,

    1
   / \
  2   3

The root-to-leaf path 1->2 represents the number 12.
The root-to-leaf path 1->3 represents the number 13.
Return the sum = 12 + 13 = 25.

有关树的recursion的题目， 题目要求的是从root到leaf，直上直下的路径，这种路径首先想到的是利用inorder的遍历相当于dfs，但是这题利用常规的inorder遍历是不行的，因为到某个叶节点的时候，就需要将这条path的值加入sum里面了，不能再去遍历叶节点的左孩子和右孩子，所以在Inorder遍历的基础上进行修改代码。
how to get every path from root to leaf??? just inorder dfs。
class Solution {
private:
    void inorder(TreeNode* root, int &sum, int path) {
        if (root == NULL) return;
        if (root->left == NULL && root->right == NULL) {
            sum += path*10 +root->val;
            return;
        }
        path = path * 10 + root->val;
        inorder(root->left, sum, path);
        inorder(root->right, sum, path);
    }
public:
    int sumNumbers(TreeNode* root) {
        //sanity check
        int sum = 0;
        inorder(root, sum, 0);
        return sum;
    }
};

path sumI:

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 true or false;


class Solution {
public:
    bool hasPathSum(TreeNode* root, int sum) {
        //sanity check
        if(root == NULL) return false;
        if (!root->left && !root->right) {
            sum -= root->val;
            if (sum == 0) return true;
        }
        sum -= root->val;
        if (hasPathSum(root->left, sum)) return true;
        if (hasPathSum(root->right, sum)) return true;
        return false;
    }
};

path Sum II

return

[
   [5,4,11,2],
   [5,8,4,5]
] 

class Solution {
private:
    void DFS(vector<vector<int>> &rst, vector<int> solu, TreeNode* root, int sum) {
        //base case
        if (root == NULL) return;
        if (!root->left && !root->right) {
            sum -= root->val;
            if (sum == 0) {
                solu.push_back(root->val);
                rst.push_back(solu);
                return;
            }
        }
        solu.push_back(root->val);
        sum -= root->val;
        DFS(rst, solu, root->left, sum);
        DFS(rst, solu, root->right, sum);
        solu.pop_back();
    }
public:
    vector<vector<int>> pathSum(TreeNode* root, int sum) {
        vector<int> solu;
        vector<vector<int>> rst;
        DFS(rst, solu, root, sum);
        return rst;
    }
}; 

以上的题目都是从root 出发一直到leaf的路径的解法， 即用常见的DFS来解， base case 要分： 

root == NULL， root左右子树均为空说明到达了树的leaf 节点。