leetcode刷题笔记一百二十四题 二叉树中的最大路径和

leetcode刷题笔记一百二十四题 二叉树中的最大路径和

源地址：124. 二叉树中的最大路径和

问题描述：

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

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

示例 1:

输入: [1,2,3]

  1
 / 
2   3

输出: 6
示例 2:

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

-10
/
9 20
/
15 7

输出: 42

/**
本题使用递归的方法，递归的过程中对Sum不断更新
*/
/**
 * Definition for a binary tree node.
 * class TreeNode(var _value: Int) {
 *   var value: Int = _value
 *   var left: TreeNode = null
 *   var right: TreeNode = null
 * }
 */
object Solution {
    def maxPathSum(root: TreeNode): Int = {
        var ans = Int.MinValue
        def helper(root: TreeNode): Int = {
            //递归出口
            if (root == null) return 0
            //只选取正值
            val leftValue = Math.max(helper(root.left), 0)
            val rightValue = Math.max(helper(root.right), 0)
            //更新结果
            ans = Math.max(ans, root.value + leftValue + rightValue)
            //进入单支结点或叶结点，返回子树计算结果
            return root.value + Math.max(leftValue, rightValue)
        }

        //var ans = Int.MinValue
        helper(root)
        return  ans 
    }
}