代码拉取完成,页面将自动刷新
package com.hit.basmath.interview.top_interview_questions.hard_collection.trees_and_graphs;
import com.hit.common.TreeNode;
/**
* 124. 二叉树中的最大路径和
* <p>
* 给定一个非空二叉树,返回其最大路径和。
* <p>
* 本题中,路径被定义为一条从树中任意节点出发,沿父节点-子节点连接,达到任意节点的序列。该路径至少包含一个节点,且不一定经过根节点。
* <p>
* 示例 1:
* <p>
* 输入:[1,2,3]
* <p>
* 1
* / \
* 2 3
* <p>
* 输出:6
* <p>
* 示例 2:
* <p>
* 输入:[-10,9,20,null,null,15,7]
* <p>
* -10
* / \
* 9 20
* / \
* 15 7
* <p>
* 输出:42
*/
public class _124 {
private int maxValue = Integer.MIN_VALUE;
public int maxPathSum(TreeNode root) {
maxPathDown(root);
return maxValue;
}
private int maxPathDown(TreeNode node) {
if (node == null) return 0;
int left = Math.max(0, maxPathDown(node.left));
int right = Math.max(0, maxPathDown(node.right));
maxValue = Math.max(maxValue, left + right + node.val);
return Math.max(left, right) + node.val;
}
}
此处可能存在不合适展示的内容,页面不予展示。您可通过相关编辑功能自查并修改。
如您确认内容无涉及 不当用语 / 纯广告导流 / 暴力 / 低俗色情 / 侵权 / 盗版 / 虚假 / 无价值内容或违法国家有关法律法规的内容,可点击提交进行申诉,我们将尽快为您处理。