当前位置: 面试刷题>> 二叉树中的最大路径和(经典算法150题)


题目描述

给定一个二叉树,其中每个节点的值都是整数。二叉树中的一条路径被定义为从根节点开始,沿着左子树或右子树,经过一系列节点,直到叶子节点(即没有子节点的节点)为止的路径。路径上所有节点的值之和称为该路径的和。求二叉树中所有路径中的最大路径和。

注意:路径不一定非得经过根节点,但路径上至少包含一个节点。此外,路径上的节点数没有限制,可以是单个节点,也可以是整棵树。

示例

给定二叉树:

   1
  / \
 2  -3

路径 1 -> 2 的和为 3,是最大路径和。

解题思路

要解决这个问题,我们需要对每个节点进行后序遍历(左子树 -> 右子树 -> 根节点),并在遍历过程中计算每个节点作为根的子树中的最大单边路径和(只考虑左子树或右子树中的最大路径)。同时,我们需要记录遍历过程中遇到的最大路径和,该路径和可能跨越根节点,也可能不跨越。

PHP 示例代码

class TreeNode {
    public $val;
    public $left;
    public $right;

    function __construct($val = 0, $left = null, $right = null) {
        $this->val = $val;
        $this->left = $left;
        $this->right = $right;
    }
}

function maxPathSum($root) {
    global $maxSum;
    $maxSum = PHP_INT_MIN;
    dfs($root);
    return $maxSum;

    function dfs($node) {
        if ($node === null) return 0;

        $leftMax = max(0, dfs($node->left));
        $rightMax = max(0, dfs($node->right));

        $priceNewPath = $node->val + $leftMax + $rightMax;
        $maxSum = max($maxSum, $priceNewPath);

        return $node->val + max($leftMax, $rightMax);
    }
}

// 使用示例
$root = new TreeNode(1);
$root->left = new TreeNode(2);
$root->right = new TreeNode(-3);
echo maxPathSum($root); // 输出 3

Python 示例代码

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def maxPathSum(root):
    global max_sum
    max_sum = float('-inf')
    def dfs(node):
        if not node:
            return 0
        
        left_max = max(dfs(node.left), 0)
        right_max = max(dfs(node.right), 0)
        
        price_new_path = node.val + left_max + right_max
        nonlocal max_sum
        max_sum = max(max_sum, price_new_path)
        
        return node.val + max(left_max, right_max)
    
    dfs(root)
    return max_sum

# 使用示例
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(-3)
print(maxPathSum(root))  # 输出 3

JavaScript 示例代码

function TreeNode(val, left, right) {
    this.val = (val===undefined ? 0 : val)
    this.left = (left===undefined ? null : left)
    this.right = (right===undefined ? null : right)
}

let maxSum = -Infinity;

function maxPathSum(root) {
    dfs(root);
    return maxSum;

    function dfs(node) {
        if (!node) return 0;

        let leftMax = Math.max(dfs(node.left), 0);
        let rightMax = Math.max(dfs(node.right), 0);

        let priceNewPath = node.val + leftMax + rightMax;
        maxSum = Math.max(maxSum, priceNewPath);

        return node.val + Math.max(leftMax, rightMax);
    }
}

// 使用示例
let root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(-3);
console.log(maxPathSum(root)); // 输出 3

通过这些示例代码,你可以看到如何递归地求解二叉树中的最大路径和。每个示例都采用了全局变量(或闭包)来记录最大路径和,并在后序遍历过程中更新这个值。

推荐面试题