[LeetCode] Binary Tree Maximum Path Sum

Given a binary tree, find the maximum path sum.

The path may start and end at any node in the tree.

For example:
Given the below binary tree,

       1
      / \
     2   3

Return 6.

思路：
1. 与常规path sum不同，这题的path sum可以不起始于root，也可以不终止于leaf。

2. 这样的path可以归纳为两种情况：
(1) root->leaf path中的一段：即题目例子中的1-2或1-3。
(2) 两个节点之间经过它们lowest common ancestor (LCA)的path：即题目中的2-1-3。

3. 显然top-down的递归并不适用于这题，因为对于类型(2)的path，它的path sum同时取决于LCA左右sub path的最大值。而这样的path sum是无法通过top-down传递来获取的。

4. 所以这里可以采用bottom-up的递归方法:
对于节点x:
定义PS1(x)为从x出发向leaf方向的第一类path中最大的path sum。
定义PS2(x)为以x为LCA的第二类path中的最大path sum。
显然如果我们求得所有节点x的PS1 & PS2，其中的最大值必然就是要求的max path sum。

5. 如何求PS1(x)、PS2(x)?
(1) PS1(x) 、PS2(x)至少应该不小于x->val，因为x自己就可以作为一个单节点path。
(2) PS1(x) 、 PS2(x)可以从PS1(x->left)和PS1(x->right)来求得：
PS1(x) = max [ max(PS1(x->left), 0), max(PS1(x->right), 0) ] + x->val
PS2(x) = max(PS1(x->left), 0) + max(PS1(x->right), 0) + x->val
注意这里并不需要PS2(x->left) 以及 PS2(x->right) 因为子节点的2型path无法和父节点构成新的path。

6. 需要返回PS1(x)以供上层的节点计算其PS1 & PS2.

7. 对于leaf节点：PS1(x) = PS2(x) = x->val.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24

class Solution { public: int maxPathSum(TreeNode *root) { int maxSum = INT_MIN; int ps1_root = findMaxPathSum(root, maxSum); return maxSum; } int findMaxPathSum(TreeNode *root, int &maxSum) { if(!root) return 0; int ps1_left = 0, ps1_right = 0; if(root->left) ps1_left = max(findMaxPathSum(root->left,maxSum),0); if(root->right) ps1_right = max(findMaxPathSum(root->right,maxSum),0); int ps1_root = max(ps1_left, ps1_right) + root->val; int ps2_root = ps1_left + ps1_right + root->val; maxSum = max(maxSum,max(ps1_root, ps2_root)); return ps1_root; } };

总结：

1. 解题的关键在于对path的分类以及应用top-down recursion。

2. 注意的细节是当x->left或x->right的第一类path sum为负数时，则这类path不应该传递到x：ln 13-16。

3. 代码并没有特殊处理leaf节点的情况。因为当root->left和root->right都不存在时，ps1_left和ps1_right均为初始值0：ln 12。于是ps1_root = ps2_root = root->val。

[LeetCode] Path Sum I, II

Path Sum I

Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum.

For example:
Given the below binary tree and sum = 22,

              5
             / \
            4   8
           /   / \
          11  13  4
         /  \      \
        7    2      1

return true, as there exist a root-to-leaf path 5->4->11->2 which sum is 22.

Path Sum II

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

思路：

1. 和min/max depth那两题类似，同样属于binary tree root->leaf path类的题目。思路也是递归，直到找到leaf为止。

2. 传递的path变量：

(1) 可以是当前path上已经访问过的所有节点的sum。这样到leaf时判断是否与目标sum相等。

(2) 也可以是目标sum减去当前path上已经访问的所有节点的sum。这样到leaf时，只要判断leaf节点的值是否等于传递下来的剩余sum即可。

Path Sum I

1 2 3 4 5 6 7 8 9 10 11 12 13 14

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

Path Sum II

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27

class Solution { public: vector<vector<int> > pathSum(TreeNode *root, int sum) { vector<int> path; vector<vector<int> > allPaths; finaPathSum(root, sum, path, allPaths); return allPaths; } void finaPathSum(TreeNode *root, int sum, vector<int> &path, vector<vector<int> > &allPaths) { if(!root) return; sum -= root->val; path.push_back(root->val); if(!root->left && !root->right) { if(sum==0) { allPaths.push_back(path); } } else { if(root->left) finaPathSum(root->left, sum, path, allPaths); if(root->right) finaPathSum(root->right, sum, path, allPaths); } path.pop_back(); } };

总结：

1. Path Sum I和II的思路基本是一样的。区别在于I只需要任意找到一条符合条件的path，就可结束查找。所以ln 10 & 11只需要在左或右子树中找到了一条path，就可以return true将结果传递回去。而对于II来说，由于需要找到所有符合条件的path，ln 21 & 22则必须同时搜索左右子树。

2. Path Sum II要求返回所有路径的集合。这也是很常见的一种函数返回类型要求。通常的做法是用一个一维vector变量存储当前解(path)，用一个二维vector存储最终的解集合(allPaths)。每层递归不断更新当前解，直到递归结束找到解后更新解集合。

3. Path Sum II中要注意ln 25对path的reset。无论递归是否结束，或者解是否找到，都不能在返回前遗漏这一步reset。因为通过当前节点的所有path已经都访问到了，返回前需要从path中删除当前节点，以便重新构建其他path。

4. 这类int求和问题都可能存在overflow的问题。需要和面试官交流明确是否程序中要检查。