注意：
// 注意,如果一个类放在另一个类里面,初始化时候会报错 Solution is not a enclosing class // 这是因为如果TreeNode不是static,那么要求先有外部类的实例 // 要加上static // 或者放到类的外面
https://leetcode.com/problems/binary-tree-maximum-path-sum/https://leetcode.com/mockinterview/session/result/xslp8c2/package com.company;import java.util.ArrayList;import java.util.List;class Solution { // 注意,如果放在Solution里面,会报错 Solution is not a enclosing class // 这是因为如果TreeNode不是static,那么要求先有外部类的实例 // 要加上static static class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(int x) { val = x; } } public int maxPathSum(TreeNode root) { // 要求至少有一个元素,全是负数情况下不能认为是0 if (root == null) { return 0; } List ret = impl(root); return ret.get(1); } // 多值返回一般放在容器里 // [0]包含root的单一路径最大值; [1] 最大值; // 调用时保证root不会为null private List impl(TreeNode root) { List ret = new ArrayList(); int maxWithRoot = root.val; int maxRet = root.val; if (root.left != null) { List left = impl(root.left); System.out.printf("Here is left %d, ret: %d, %d\n", root.left.val, left.get(0), left.get(1)); if (left.get(0) > 0) { maxWithRoot = root.val + left.get(0); } maxRet = maxWithRoot > left.get(1) ? maxWithRoot : left.get(1); } if (root.right != null) { List right = impl(root.right); int tmp = maxWithRoot; if (root.val + right.get(0) > maxWithRoot) { maxWithRoot = root.val + right.get(0); } // 下面这个地方因为考虑不周,导致了一个bug,只考虑了maxWithRoot,没有考虑之前的maxRet maxRet = maxWithRoot > maxRet ? maxWithRoot : maxRet; maxRet = maxRet > right.get(1) ? maxRet : right.get(1); // merge two branch if (tmp + right.get(0) > maxRet) { maxRet = tmp + right.get(0); } } ret.add(maxWithRoot); ret.add(maxRet); System.out.printf("Here is node %d, ret: %d, %d\n", root.val, maxWithRoot, maxRet); return ret; }}public class Main { public static void main(String[] args) { // write your code here System.out.println("Hello"); Solution.TreeNode node1 = new Solution.TreeNode(1); Solution.TreeNode node2 = new Solution.TreeNode(2); Solution.TreeNode node3 = new Solution.TreeNode(3); Solution.TreeNode node4 = new Solution.TreeNode(4); Solution.TreeNode node5 = new Solution.TreeNode(5); Solution.TreeNode node6 = new Solution.TreeNode(6); Solution.TreeNode node7 = new Solution.TreeNode(7); Solution.TreeNode node8 = new Solution.TreeNode(8); Solution.TreeNode node9 = new Solution.TreeNode(9); Solution.TreeNode node10 = new Solution.TreeNode(10); node1.left = node2; node1.right = node3; node2.left = node4; node2.right = node5; node3.left = node6; node3.right = node7; node4.left = node8; node4.right = node9; node5.left = node10; Solution solution = new Solution(); int ret = solution.maxPathSum(node1); System.out.printf("Get ret: %d\n", ret); }}