题解 | #二叉树中的最大路径和#
二叉树中的最大路径和
https://www.nowcoder.com/practice/da785ea0f64b442488c125b441a4ba4a
/* * function TreeNode(x) { * this.val = x; * this.left = null; * this.right = null; * } */ /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param root TreeNode类 * @return int整型 */ function maxPathSum( root ) { // write code here let maxSum = Number.MIN_SAFE_INTEGER; function maxPathSumRes(node) { if (node == null) { return 0; } let leftTree = Math.max(maxPathSumRes(node.left), 0); let rightTree = Math.max(maxPathSumRes(node.right), 0); const sum = node.val + leftTree + rightTree; maxSum = Math.max(maxSum, sum); return node.val + Math.max(leftTree, rightTree); } maxPathSumRes(root); return maxSum; } module.exports = { maxPathSum : maxPathSum };
每次递归查找的时候更新最大值。
每次统计左子树+根+右子树,(注意:子树返回负数则不考虑)
返回其中一个子树+根当做一个最优路径。