Skip to main content

124. Binary Tree Maximum Path Sum

分析

这道题的有趣之处是,结点是有两种用途的

题解

function maxPathSum(root: TreeNode | null): number {
let ans = -Infinity

const dfs = (node: TreeNode | null) => {
if (!node) {
return 0
}
const left = dfs(node.left)
const right = dfs(node.right)

// 作为根节点的时候,两边的树都能用
ans = Math.max(
ans,
node.val,
node.val + Math.max(left, right),
node.val + left + right
)

// 作为子树的时候 三种选择 选择 1. 停在根 2. 向右 3. 向左
return Math.max(node.val, node.val + left, node.val + right)
}

dfs(root)

return ans
};