## Monday, August 8, 2016

### Google – Binary Tree Maximum Path Without Consecutive Nodes

Google – Binary Tree Maximum Path Without Consecutive Nodes
Leetcode 124 Binary Tree Maximum Path Sum的变形。区别就是不能有连续的node。
[Analysis]

[Solution]

[Note]
1. return两个值需要用个class来wrap
2. 注意和0的比较，在extend current node的时候，只有当left.without或right.without大于0的情况下才能extend, 否则即使当前节点为负数，继续extend只会让path sum更小。
3. 而当不考虑当前节点的时候，最大path sum也不一定就是left.with或者right.with. left.without和right.without一样也可以是不考虑当前节点情况下的最大path sum.
`class` `Solution {`
`  ``int` `result = ``0``;`
`  ``public` `int` `maxPathSum(TreeNode root) {`
`    ``if` `(root == ``null``) {`
`      ``return` `0``;`
`    ``}`

`    ``dfs(root);`
`    ``return` `result;`
`  ``}`

`  ``private` `Pair dfs(TreeNode root) {`
`    ``if` `(root == ``null``) {`
`      ``return` `null``;`
`    ``}`
`    ``if` `(root.left == ``null` `&& root.right == ``null``) {`
`      ``return` `new` `Pair(root.val, ``0``);`
`    ``}`

`    ``Pair left = dfs(root.left);`
`    ``Pair right = dfs(root.right);`

`    ``// with curr node`
`    ``int` `curr = root.val;`
`    ``if` `(left.without > ``0``) curr += left.without;`
`    ``if` `(right.without > ``0``) curr += right.without;`
`    ``result = Math.max(result, curr);`

`    ``// without curr node`
`    ``curr = ``0``;`
`    ``curr += Math.max(``0``, Math.max(left.with, left.without));`
`    ``curr += Math.max(``0``, Math.max(right.with, right.without));`
`    ``result = Math.max(result, curr);`

`    ``// generate return pair`
`    ``int` `withCurr = root.val;`
`    ``withCurr += Math.max(``0``, Math.max(left.without, right.without));`
`    ``int` `withoutCurr = ``0``;`
`    ``withoutCurr = Math.max(withoutCurr, Math.max(left.with, left.without));`
`    ``withoutCurr = Math.max(withoutCurr, Math.max(right.with, right.without));`

`    ``return` `new` `Pair(withCurr, withoutCurr);`
`  ``}`

`  ``private` `class` `Pair {`
`    ``int` `with;`
`    ``int` `without;`

`    ``Pair(``int` `with, ``int` `without) {`
`      ``this``.with = with;`
`      ``this``.without = without;`
`    ``}`
`  ``}`
`}`