每日题解:LeetCode 124. 二叉树中的最大路径和

Author Avatar
清水雅然君 06月 21,2020

题目地址

题目描述

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

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

示例 1:

输入: [1,2,3]

       1
      / \
     2   3

输出: 6
示例 2:

输入: [-10,9,20,null,null,15,7]

   -10
   / \
  9  20
    /  \
   15   7

输出: 42

解法

public class Solution {
    int sum=Integer.MIN_VALUE;
    public int maxPathSum(TreeNode root) {
      findMax(root);
      return sum;
    }

    private int findMax(TreeNode node) {
        if(node==null){
            return 0;
        }
        int leftSum = Math.max(findMax(node.left), 0);
        int rightSum = Math.max(findMax(node.right), 0);
        int nodeSum = node.val + leftSum + rightSum;
        sum = Math.max(sum, nodeSum);
        return node.val + Math.max(leftSum, rightSum);
    }
}

解题思路

递归

首先我们先搬出递归的模板

public Node findMax(...){
    //...逻辑
    root = ...
    //...逻辑
    root.left = ...
    //...逻辑
    root.right = ...
    //...逻辑
    return root;
}

二叉树 abc,a 是根结点,bc 是左右子结点,求其最大的路径,可能的路径情况:

    a
   / \
  b   c

1.b + a + c
2.b + a
3.a + c
可能存在a节点为负数的情况,那么我们就需寻找三种情况中的最大值就可以了
递归的结束

//不存在的节点,我们设置为0.比如叶节点的的算最大路径时,没有左右节点,不影响计算结果
if(node==null){
return 0;
}

需要左右路径的最大值

//利用 Math.max(x,0)将负节点去掉
 int leftSum = Math.max(findMax(node.left), 0);
int rightSum = Math.max(findMax(node.right), 0);

然后获取当前节点的最大路径值

int nodeSum = node.val + leftSum + rightSum;

然后我们命名一个遍历sum,保存结果的最大值,一开始我将sum的初始化设置为0;但是遇到只要一个根节点的并且节点是负数测试用例(再次说,李姐万岁)!,索性就将初始化设置为最小

//存在单个节点为负数的情况,不能确定其值
    int sum=Integer.MIN_VALUE;

最后就是替换我们的模板中的关键点

    int sum=Integer.MIN_VALUE;
    
    private int findMax(TreeNode node) {
        if(node==null){
            return 0;
        }
        int leftSum = Math.max(findMax(node.left), 0);
        int rightSum = Math.max(findMax(node.right), 0);
        int nodeSum = node.val + leftSum + rightSum;
        sum = Math.max(sum, nodeSum);
        //返回节点的最大值
        return node.val + Math.max(leftSum, rightSum);
    }

题目虽然时困难程度,但是实际解决中,并不是很复杂,一般关于树的题目,使用递归(深度)或者迭代(层的计算)比较多,比如之前的,1457. 二叉树中的伪回文路径,需要遍历树的深度就使用了递归;
226. 翻转二叉树,需要对层进行处理,使用迭代就比较清晰