Path Sum i 要求判断是否存在和为sum的root->leaf路径
https://leetcode.com/problems/path-sum/
Path Sum ii 要求输出和为sum的root->leaf路径
https://leetcode.com/problems/path-sum-ii/
Similar Problem:
257.Binary Tree Paths 输出所有root->leaf路径
https://leetcode.com/problems/binary-tree-paths/
129.Sum Root to Leaf Numbers 每条root->leaf求和再求和
https://leetcode.com/problems/sum-root-to-leaf-numbers/
124.Binary Tree Maximum Path Sum
https://leetcode.com/problems/binary-tree-maximum-path-sum/

1.Path Sum i

dfs，递归

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {

public:
    bool hasPathSum(TreeNode* root, int sum) {
        if(root == NULL) {
            return false;
        }
        if(root->left == NULL && root->right == NULL) {
            if(sum == root->val)
                return true;
            else 
                return false;
        }
        return hasPathSum(root->left, sum - root->val) || hasPathSum(root->right, sum - root->val);
    }
};    

dfs，非递归
必须是post order，最后再减掉

class Solution {
public:
    bool hasPathSum(TreeNode* root, int sum) {
        if(root == NULL) return false;
        int num = 0;
        stack<TreeNode *> st;
        TreeNode * p = root;
        TreeNode * pre = NULL;
        while(!st.empty() || p!=NULL) {
            if(p!=NULL) {
                st.push(p);
                num += p->val;
                if(!p->left && !p->right && num == sum) {
                    return true;
                }
                p = p->left;
            } else {
                TreeNode * n = st.top(); 
                if(n->right != pre && n->right != NULL){
                    p = n->right;
                } else {
                    st.pop();
                    pre = n;
                    num -= n->val;
                }
            }
        }
        return false;
    }
};    

2.Path Sum ii

dfs 回溯

class Solution {
    void helper(vector<vector<int>>& res, vector<int> & now, TreeNode * root, int sum) {
        if(!root) return;
        now.push_back(root->val);
        if(root->left == NULL && root->right == NULL && root->val == sum) {
            res.push_back(now);
        }
        helper(res, now, root->left, sum - root->val);
        helper(res, now, root->right, sum - root->val);
        now.pop_back();
    }
public:
    vector<vector<int>> pathSum(TreeNode* root, int sum) {
        vector<vector<int>> res;
        vector<int> now;
        helper(res, now, root, sum);
        return res;
    }
};

dfs 非递归

class Solution {
public:
    vector<vector<int>> pathSum(TreeNode* root, int sum) {
        vector<vector<int>> ret;
        if(root == NULL) return ret;
        vector<int> now;
        int num = 0;
        stack<TreeNode *> st;
        TreeNode * p = root;
        TreeNode * pre = NULL;
        while(p != NULL || !st.empty()) {
            if(p != NULL) {
                st.push(p);
                now.push_back(p->val);
                num += p->val;
                if(!p->left && !p->right && num == sum) {
                    ret.push_back(now);
                }
                p = p->left;
            } else {
                TreeNode * n = st.top();
                if(n->right != NULL && n->right != pre) {
                    p = n->right;
                } else {
                    st.pop();
                    pre = n;
                    num -= n->val;
                    now.pop_back();
                }
            }
        }
        return ret;
    }
};

124.Binary Tree Maximum Path Sum
不需要经过root
是否需要经过叶子节点？
起始节点是任意的吗？

如果要求经过叶子节点：

class Solution {
    int maxSum;
    int helper(TreeNode * root) {
        if(!root) return 0;
        int l = helper(root->left);
        int r = helper(root->right);
        int m = max(l, r);
        maxSum = max(maxSum, l + root->val + r);
        return m + root->val;
    }
public:
    int maxPathSum(TreeNode* root) {
        maxSum = INT_MIN;
        helper(root);
        return maxSum;
    }
};

如果不要求经过叶子节点，只需要判断是否小于0：

class Solution {
    int maxSum;
    int helper(TreeNode * root) {
        if(!root) return 0;
        int l = max(helper(root->left),0);
        int r = max(helper(root->right),0);
        int m = max(l, r);
        maxSum = max(maxSum, l + root->val + r);
        return m + root->val;
    }
public:
    int maxPathSum(TreeNode* root) {
        maxSum = INT_MIN;
        helper(root);
        return maxSum;
    }
};