LeetCode - Hard - 124. Binary Tree Maximum Path Sum-蒲公英云

LeetCode - Hard - 124. Binary Tree Maximum Path Sum

Topic

Tree
Depth-first Search
Recursion

Description

https://leetcode.com/problems/binary-tree-maximum-path-sum/

A path in a binary tree is a sequence of nodes where each pair of adjacent nodes in the sequence has an edge connecting them. A node can only appear in the sequence at most once. Note that the path does not need to pass through the root.

The path sum of a path is the sum of the node’s values in the path.

Given the root of a binary tree, return the maximum path sum of any path.

Example 1:

Input: root = [1,2,3]
Output: 6
Explanation: The optimal path is 2 -> 1 -> 3 with a path sum of 2 + 1 + 3 = 6.

Example 2:

Input: root = [-10,9,20,null,null,15,7]
Output: 42
Explanation: The optimal path is 15 -> 20 -> 7 with a path sum of 15 + 20 + 7 = 42.

Constraints:

The number of nodes in the tree is in the range [ 1 , 3 ∗ 1 0 4 ] [1, 3 * 10^4] [1,3∗104].
− 1000 < = N o d e . v a l < = 1000 -1000 <= Node.val <= 1000 −1000<=Node.val<=1000

Analysis

判断两节点之间节点值和，最好从树叶到树根的遍历方式，所以用二叉树的后序遍历模式。

方法一：我写的。

方法二：别人写的，优雅了许多。

方法二中，当父节点值与左右子孙节点和值相加时，如果左右子孙节点和值是负数，那么干脆不采用它，也就是用0代替这节点值（如和为-9，它的父节点为n， n + ( − 9 ) < n + 0 n + (-9) < n + 0 n+(−9)<n+0

Submission

import com.lun.util.BinaryTree.TreeNode;
public class BinaryTreeMaximumPathSum { 
    private static int MIN_VALUE = -1001;//不用Integer.MIN_VALUE，原因是用它可能造成溢出情况
    //方法一：我写的
    public int maxPathSum(TreeNode root) { 
        int[] maxAlone = { MIN_VALUE};
        int max = maxPathSum(root, maxAlone);
        return Math.max(maxAlone[0], max);
    }
    private int maxPathSum(TreeNode node, int[] maxAlone) { 
        if(node == null) return MIN_VALUE;
        int leftMax = maxPathSum(node.left, maxAlone);
        int rightMax = maxPathSum(node.right, maxAlone);
        int maxOne = Math.max(Math.max(leftMax, rightMax), //
                leftMax + rightMax + node.val); 
        if(maxOne > maxAlone[0]) { 
            maxAlone[0] = maxOne;
        }
        return Math.max(Math.max(leftMax + node.val, rightMax + node.val),// 
                node.val);
    }
    //方法二：别人写的
    public int maxPathSum2(TreeNode root) { 
        int[] max = { Integer.MIN_VALUE};
        maxPathSum2(root, max);
        return max[0];
    }
    private int maxPathSum2(TreeNode node, int[] max) { 
        if (node == null) return 0;
        //如果节点值是负数，那么干脆不采用这节点值，也就是用0代替这节点值
        //（如节点值为-9，它的父节点为n，n+(-9) < n + 0
        int leftMax = Math.max(0, maxPathSum2(node.left, max));
        int rightMax = Math.max(0, maxPathSum2(node.right, max));
        max[0] = Math.max(max[0], leftMax + rightMax + node.val);
        return Math.max(leftMax, rightMax) + node.val;
    }
}

Test

import static org.junit.Assert.*;
import org.junit.Test;
import com.lun.util.BinaryTree;
public class BinaryTreeMaximumPathSumTest { 
    @Test
    public void test() { 
        BinaryTreeMaximumPathSum obj = new BinaryTreeMaximumPathSum();
        assertEquals(6, obj.maxPathSum(BinaryTree.integers2BinaryTree(1, 2, 3)));
        assertEquals(42, obj.maxPathSum(BinaryTree.integers2BinaryTree(-10, 9, 20, null, null, 15, 7)));
        assertEquals(-3, obj.maxPathSum(BinaryTree.integers2BinaryTree(-3)));
        assertEquals(1, obj.maxPathSum(BinaryTree.integers2BinaryTree(-2, 1)));
        assertEquals(10, obj.maxPathSum(BinaryTree.integers2BinaryTree(-1,-2,10,-6,null,-3,-6)));
    }
    @Test
    public void test2() { 
        BinaryTreeMaximumPathSum obj = new BinaryTreeMaximumPathSum();
        assertEquals(6, obj.maxPathSum2(BinaryTree.integers2BinaryTree(1, 2, 3)));
        assertEquals(42, obj.maxPathSum2(BinaryTree.integers2BinaryTree(-10, 9, 20, null, null, 15, 7)));
        assertEquals(-3, obj.maxPathSum2(BinaryTree.integers2BinaryTree(-3)));
        assertEquals(1, obj.maxPathSum2(BinaryTree.integers2BinaryTree(-2, 1)));
        assertEquals(10, obj.maxPathSum2(BinaryTree.integers2BinaryTree(-1,-2,10,-6,null,-3,-6)));
    }
}