leetcode hot 100-124. 二叉树中的最大路径和

124. 二叉树中的最大路径和

题目描述

给定一个非空二叉树，返回其最大路径和。

本题中，路径被定义为一条从树中任意节点出发，沿父节点-子节点连接，达到任意节点的序列。该路径至少包含一个节点，且不一定经过根节点。

示例 1：

示例 2：

思路：递归

思路参考：https://leetcode-cn.com/problems/binary-tree-maximum-path-sum/solution/er-cha-shu-zhong-de-zui-da-lu-jing-he-by-ikaruga/

每棵子树的最大路径等于根节点加上左右子树的最大路径，如果左右子树的最大路径小于0，则加上0，而非加上左右子树。因为如果左右子树最大值小于0的话，加上他们也是一个拖累，所以如果小于0，则不加他们，而是加上0。如果左右子树最大路径均小于0，则当前子树的最大路径就是根节点的值，所以单个结点为最大路径的情况在每个结点为根节点时就应经考虑到了。

但是返回值只能返回子树的半边或者只返回根节点

 1 class Solution {
 2 
 3     public int maxSum = -1 << 30;
 4     public int inOrder(TreeNode root){
 5         if(root == null){
 6             return 0;
 7         }
 8         int leftMaxSum = inOrder(root.left);
 9         int rightMaxSum = inOrder(root.right);
10        
11         // 最大值在根节点加上左右根节点
12         int sum = root.val + Math.max(leftMaxSum, 0) + Math.max(rightMaxSum, 0);    
13         int ret = root.val + Math.max(Math.max(leftMaxSum, rightMaxSum), 0);
14         maxSum  = Math.max(sum, maxSum);
15         return ret;     // 只返回该子树半边或者只返回根节点
16     }
17 
18     public int maxPathSum(TreeNode root) {
19 
20         // 左右根中序递归遍历
21         inOrder(root);
22         // 维护一个最大值，返回子树根节点的值加上0或者左右子树的最大值
23         return maxSum;
24     }
25 }

leetcode 执行用时：1 ms > 99.78%, 内存消耗：40 MB > 98.55%

复杂度分析：

时间复杂度：O(n)。遍历了所有的结点，所以时间复杂度为O(n)。

空间复杂度：O(n)。空间复杂度取决于递归栈的深度，递归栈的深度取决于树的高度，树的高度最大为 n, 即退化成链表时，所以空间复杂度为最差为O(n)。