⭐️ 题目日期：

百度 - 2024/8/13

🌳 题目描述：

给定一个二叉树，返回从一个叶子节点到另一个叶子节点最大路径的和。

示例 1：

输入：root = [2, 1, 3, 0, 1, 3, 5]

输出：12

图解如下：

🕵🏽 面试评估：

这道题考察候选人能否利用递归，深度优先搜索（DFS）来处理二叉树的遍历，并在递归过程中处理路径的累加和以及最大值的更新。

🧗难度系数：

⭐️ ⭐️ ⭐️ ⭐️

📝思路分析：

问题分析：

解决树的路径问题需要考虑三个核心问题：

你需要左右子树给你什么信息

当前节点拿到左右子树的信息，如何处理，返回有用的信息给上一层

重复1, 2, 何时停止

以上的三个问题对应递归三要素的基准、分解以及求解。那我们分别来回答以上的核心问题

你需要左右子树给你什么信息

需要从左子树拿到最大的单边路径，同理，需要从右子树拿到最大的单边路径。

备注：何为单边路径，从叶子节点到另一个叶子节点组成的路径会汇聚一个节点。例如路径：1 - 1 - 2 - 3 - 5。其中1 - 1 和 5 - 3都为单边路径，他们汇聚于节点2

当前节点拿到左右子树的信息，如何处理，返回有用的信息给上一层

a. 如果左右子树都存在单边路径，再加上当前的节点，那就组合成了一个从叶节点到另一个叶节点的路径，更新结果

b. 然后再将当前的节点拼接到左右路径较大的单边路径组合成一个新的单边路径，返回给上一层。（告诉父节点：这是到我这为止的最大单边路径，需要的话可以拿去用）

何时停止

当节点为空的时候，返回0；0的值也不会影响如果有负数的结果，因为在上一层可以判断左右子树是否为空，从而判断是否返回了单边路径。

图解：

💻代码(Java、Python)：

Java

public int maximumLeavesPath(TreeNode root) {
    int[] res = {Integer.MIN_VALUE};
    findLargestPath(root, res);
    return res[0];
}

private int findLargestPath(TreeNode root, int[] res) {
    if (root == null) {
        return 0;
    }

    int leftLargestPath = findLargestPath(root.left, res);
    int rightLargestPath = findLargestPath(root.right, res);

    if (root.left != null && root.right != null) {
        // 如果左右子树都不为空，说明找到一条从叶子节点到另一个叶子节点的路径，更新结果
        res[0] = Math.max(res[0], leftLargestPath + rightLargestPath + root.value);

        // 从左右子树中挑一个更大的路径，加上当前节点的值，返回给上一层 （告诉父节点：这是到我这为止的最大单边路径）
        return root.value + Math.max(leftLargestPath, rightLargestPath);
    }

    // 如果左边为空，选右边的(如果右边也为空，rightLargestPath 也为0，不影响结果)；如果右边为空，选左边的；
    // 再加上自己，组成一条新的单边路径，返回给上一层 （告诉父节点：这是到我这为止的最大单边路径）
    return root.left == null ? rightLargestPath + root.value : leftLargestPath + root.value;
}

Python

def maximum_leaves_path(self, root):
    # 使用列表存储结果，以实现引用传递
    res = [float('-inf')]
    self.find_largest_path(root, res)
    return res[0]


def find_largest_path(self, root, res):
    if root is None:
        return 0

    left_largest_path = self.findLargestPath(root.left, res)
    right_largest_path = self.findLargestPath(root.right, res)

    if root.left is not None and root.right is not None:
        # 如果左右子树都不为空，说明找到一条从叶子节点到另一个叶子节点的路径，更新结果
        res[0] = max(res[0], left_largest_path + right_largest_path + root.value)

        # 返回最大单边路径（左右子树中选择最大的一条，加上当前节点的值）
        return root.value + max(left_largest_path, right_largest_path)

    # 如果只有一个子树或两个子树都为空，选不为空的一边（为 None 的子树返回 0），加上当前节点值
    return (right_largest_path + root.value if root.left is None
            else left_largest_path + root.value)

🚵🏻复杂度分析：

时间复杂度：O(n)，n 为节点个数

空间复杂度：O(h)，h 为树的深度。对于完全二叉树，树的高度为 logn, 所以空间复杂度为 O(log ⁡n)；最坏情况下，每个节点都只有一个子节点，树的高度为节点的个数，空间复杂度为 O(n)