leetcode(124) - 二叉树中的最大路径和
一、题目描述
1 英文版
Given a non-empty binary tree, find the maximum path sum.
For this problem, a path is defined as any sequence of nodes from some starting node to any node in the tree along the parent-child connections. The path must contain at least one node and does not need to go through the root.
Example 1:
Input: [1,2,3]
1
/ \
2 3
Output: 6
Example 2:
Input: [-10,9,20,null,null,15,7] -10 / \ 9 20 / \ 15 7 Output: 42
2 中文版
Given a non-empty binary tree, find the maximum path sum.
For this problem, a path is defined as any sequence of nodes from some starting node to any node in the tree along the parent-child connections. The path must contain at least one node and does not need to go through the root.
Example 1:
Input: [1,2,3]
1
/ \
2 3
Output: 6
Example 2:
Input: [-10,9,20,null,null,15,7] -10 / \ 9 20 / \ 15 7 Output: 42
二、ruby方案
1 为什么返回值是[max_left, max_right].max + root.val
[max_left, max_right].max + root.val 是当前节点为起点，子树路径的最大和；
主要是计算左子树、右子树的路径和使用，画图后很好理解，不好描述，自己画图理解；
一句话： root为起点，不能回溯。
2 代码
# Definition for a binary tree node.
# class TreeNode
# attr_accessor :val, :left, :right
# def initialize(val)
# @val = val
# @left, @right = nil, nil
# end
# end
# @param {TreeNode} root
# @return {Integer}
$res = 0
def max_path_sum(root)
max_sum(root)
return $res
end
def max_sum(root)
if root.nil?
return 0
end
max_left = [0, max_sum(root.left)].max
max_right = [0, max_sum(root.right)].max
temp = max_left + max_right + root.val
$res = [$res, temp].max
return [max_left, max_right].max + root.val
end
Show Disqus Comments