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

使用DFS来不断的往回传递包含当前节点的肯能的最大值，但是在DFS的同时需要用一个变量来维护全局最大值，主要情况可以分为：

1. 叶子节点，直接与全局最大值比较，返回自己
2. 只有一个孩子的节点，最大值可能是本身也可能是本身与一颗子树的返回值的和，因此求出较大的之后与全局比较，再返回
3. 有两个子树，那么要考虑自己，自己与左子树，自己与右子树和自己与左右子树的和，这里面最大的与全局最大比较，但是，返回的时候，自己与左右子树不能作为一条路径返回，因为路径只能选择一颗子树，因此返回自己，自己与左子树，自己与右子树的和的较大者

注意第三中情况不要写错了

    int ma = Integer.MIN_VALUE;
    public int maxPathSum(TreeNode root) {
        ma = Integer.MIN_VALUE;
        dfs(root);
        return ma;
    }
    
    private int dfs(TreeNode root) {
        if(root.left == null && root.right == null) {
            ma = Math.max(ma, root.val);
            return root.val;
        }
        else if(root.left == null && root.right != null) {
            int tmax = Math.max(root.val, root.val + dfs(root.right));
            ma = Math.max(ma, tmax);
            return tmax;
        }
        else if(root.left != null && root.right == null) {
            int tmax = Math.max(root.val, root.val + dfs(root.left));
            ma = Math.max(ma, tmax);
            return tmax;
        }
        else {
            int left = dfs(root.left);
            int right = dfs(root.right);
            int tmax = Math.max(root.val, Math.max(root.val+left, root.val+right));
            ma = Math.max(ma, Math.max(tmax, root.val+left+right));
            return tmax;
        }
    }