Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

124. 二叉树中的最大路径和 #46

Open
webVueBlog opened this issue Sep 4, 2022 · 0 comments
Open

124. 二叉树中的最大路径和 #46

webVueBlog opened this issue Sep 4, 2022 · 0 comments

Comments

@webVueBlog
Copy link
Owner

124. 二叉树中的最大路径和

Description

Difficulty: 困难

Related Topics: , 深度优先搜索, 动态规划, 二叉树

路径 被定义为一条从树中任意节点出发,沿父节点-子节点连接,达到任意节点的序列。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点,且不一定经过根节点。

路径和 是路径中各节点值的总和。

给你一个二叉树的根节点 root ,返回其 最大路径和

示例 1:

输入:root = [1,2,3]
输出:6
解释:最优路径是 2 -> 1 -> 3 ,路径和为 2 + 1 + 3 = 6

示例 2:

输入:root = [-10,9,20,null,null,15,7]
输出:42
解释:最优路径是 15 -> 20 -> 7 ,路径和为 15 + 20 + 7 = 42

提示:

  • 树中节点数目范围是 [1, 3 * 104]
  • -1000 <= Node.val <= 1000

Solution

Language: JavaScript

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
// 最大路径和为根节点+左子树+右子树的深度最大值
// 当前节点往下走的最大值分三种情况:
// 1. 往左走:当前节点+L(左子树的最大深度)
// 2. 往右走:当前节点+R(右子树的最大深度)
// 3. 不走:当前节点如果为负值,直接舍弃返回0
var maxPathSum = function(root) {
    let ans = -Infinity
    dfs(root)
    return ans

    // 从当前节点往下走
    function dfs(root) {
        // 根节点为空直接返回0
        if (!root) return 0
        // 遍历左子树的深度
        let left = dfs(root.left)
        // 遍历右子树的深度
        let right = dfs(root.right)
        // 更新路径的最大值
        ans = Math.max(ans, root.val + left + right)
        // 返回从当前节点往下走的最大值
        return Math.max(0, Math.max(left, right) + root.val)
    }
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

1 participant