Google – Binary Tree Maximum Path Without Consecutive Nodes

Related Leetcode 124 - Binary Tree Maximum Path Sum
Google – Binary Tree Maximum Path Without Consecutive Nodes
Leetcode 124 Binary Tree Maximum Path Sum的变形。区别就是不能有连续的node。
[Analysis]
有点像House Robber III, 但是House Robber规定Path只能从root开始，大大简化了题目难度。这道题的path可以是任意的，上下左右都可以，唯一的限制就是不能使用连续node。
[Solution]
思路其实就是dfs，和leetcode124是一样的，只不过在递归回parent的时候return两个值，一个是包含当前节点的最大值，另一个是不包含当前节点的最大值。
因为这道题的状态非常复杂，既要考虑包不包含，还需要考虑正负数，外加这类dfs递归题向来想不清楚，所以是道非常有价值的题，值得反复做。

[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;

    }

  }

}

Read full article from Google – Binary Tree Maximum Path Without Consecutive Nodes