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

题目描述

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

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

示例 1:

输入: [1,2,3]

    1
    / \
    2   3

输出: 6

示例 2:

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

   -10
   / \
  9  20
    /  \
   15   7

输出: 42

思路

思路1

后序遍历递归实现，最大路径只能为node+left son + right son或node + left son + node的父节点或node + right son + 父节点，所以在具体实现中后序遍历二叉数，并分别计算比较这三个值即可，递归得到以left son为最高节点的最大路径和right son为最高节点的路径和

代码

代码1

class Solution {
    private int result = Integer.MIN_VALUE;
    
    public int maxPathSum(TreeNode root) {
        maxPathCount(root);
        return result;
    }
    
    private int maxPathCount(TreeNode node){
        if (node == null){
            return 0;
        }
        
        int leftSum = Math.max(maxPathCount(node.left), 0);
        int rightSum = Math.max(maxPathCount(node.right), 0);
        
        int newSum = node.val + leftSum + rightSum;
        result = Math.max(result, newSum);
        
        return node.val + Math.max(leftSum, rightSum);
    }
}