437. Path Sum III

重点是分成两部分，一部分是包含root的路径，另一部分是不包含的。
class Solution {

public:
    // 在以root为根节点的二叉树中,寻找和为sum的路径,返回这样的路径个数
    int pathSum(TreeNode* root, int sum) {

        if( root == NULL )
            return 0;

        return findPath( root , sum )//from root
                + pathSum( root->left , sum )//from left not include root
                + pathSum( root->right , sum );//from right not include root
    }

private:

    // 在以node为根节点的二叉树中,寻找包含node的路径,和为sum
    // 返回这样的路径个数
    int findPath( TreeNode* node, int num){

        if( node == NULL )
            return 0;

        int res = 0;
        if( node->val == num )
            res += 1;

        res += findPath( node->left , num - node->val );
        res += findPath( node->right , num - node->val );

        return res;
    }
};

class Solution {
public:
    int pathSum(TreeNode* root, int sum) {
        if (!root) return 0;
        return sumUp(root, 0, sum) + pathSum(root->left, sum) + pathSum(root->right, sum);
    }
    int sumUp(TreeNode* node, int pre, int& sum) {
        if (!node) return 0;
        int cur = pre + node->val;
        return (cur == sum) + sumUp(node->left, cur, sum) + sumUp(node->right, cur, sum);
    }
};

• http://www.cnblogs.com/grandyang/p/6007336.html
• https://discuss.leetcode.com/topic/64402/c-5-line-body-code-dfs-solution