二叉树最大路径和题解

题解思路

我们可以使用深度优先搜索（DFS）的方式来递归求解。
对于每个节点，设其最大贡献值（即以该节点为起点、延伸到一侧分支上的最大路径和）为：

max_gain = node.val + max(左子树的贡献, 右子树的贡献, 0)

这里，当左右子树的贡献为负时，我们可以选择不连接（视作0），因为负数会降低路径和。

同时，节点 node 作为“拐点”时，能够形成的路径和为：

price_newpath = node.val + 左子树的贡献 + 右子树的贡献

我们在递归过程中维护一个全局变量，记录遇到的最大路径和。最终答案即为全局变量的值。

递归函数说明

• 对于每个节点，我们递归计算其左子树和右子树的最大贡献值（若为负则取0）。
• 更新全局最大路径和：
  max_sum = max(max_sum, node.val + left_gain + right_gain)
• 返回节点的最大贡献值给父节点：
  node.val + max(left_gain, right_gain)

复杂度分析

• 时间复杂度：
  每个节点仅被访问一次，因此时间复杂度为 O(n)，其中 n 为节点数。
• 空间复杂度：
  递归调用的栈空间最坏情况下为 O(n)（当二叉树退化为链表时），平均情况下为 O(log n)。

代码实现

Python 代码

# 定义二叉树节点类
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val       # 节点的值
        self.left = left     # 左子树
        self.right = right   # 右子树

def build_tree(level_order):
    if not level_order or level_order[0] == 'null':
        return None
    
    root = TreeNode(int(level_order[0]))
    queue = [root]
    i = 1
    while i < len(level_order):
        current = queue.pop(0)
        # 构造左子节点
        if i < len(level_order) and level_order[i] != 'null':
            current.left = TreeNode(int(level_order[i]))
            queue.append(current.left)
        i += 1
        # 构造右子节点
        if i < len(level_order) and level_order[i] != 'null':
            current.right = TreeNode(int(level_order[i]))
            queue.append(current.right)
        i += 1
    return root

def max_path_sum(root):
    """
    计算二叉树的最大路径和
    :param root: 二叉树根节点
    :return: 最大路径和
    """
    max_sum = float('-inf')  # 初始化全局最大路径和

    def max_gain(node):
        nonlocal max_sum
        if node is None:
            return 0
        # 递归计算左右子树的最大贡献值，负数时取0
        left_gain = max(max_gain(node.left), 0)
        right_gain = max(max_gain(node.right), 0)
        # 当前节点作为拐点时的路径和
        price_newpath = node.val + left_gain + right_gain
        # 更新全局最大路径和
        max_sum = max(max_sum, price_newpath)
        # 返回节点的最大贡献值
        return node.val + max(left_gain, right_gain)
    
    max_gain(root)
    return max_sum

if __name__ == "__main__":
    import sys
    input_data = sys.stdin.read().strip()
    tokens = input_data.split()
    root = build_tree(tokens)
    print(max_path_sum(root))

Java 代码

import java.util.*;

// 定义二叉树节点类
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) {
        val = x;
    }
}

public class Main {
    // 全局变量，记录最大路径和
    private static int maxSum = Integer.MIN_VALUE;
    
    // 根据层次遍历结果构造二叉树
    public static TreeNode buildTree(String[] tokens) {
        if (tokens.length == 0 || tokens[0].equals("null"))
            return null;
        
        TreeNode root = new TreeNode(Integer.parseInt(tokens[0]));
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        int i = 1;
        while (i < tokens.length) {
            TreeNode current = queue.poll();
            // 构造左子节点
            if (i < tokens.length && !tokens[i].equals("null")) {
                current.left = new TreeNode(Integer.parseInt(tokens[i]));
                queue.offer(current.left);
            }
            i++;
            // 构造右子节点
            if (i < tokens.length && !tokens[i].equals("null")) {
                current.right = new TreeNode(Integer.parseInt(tokens[i]));
                queue.offer(current.right);
            }
            i++;
        }
        return root;
    }
    
    // 递归计算从当前节点出发的最大贡献值
    private static int maxGain(TreeNode node) {
        if (node == null)
            return 0;
        // 递归计算左右子树的贡献值，若为负则置为0
        int leftGain = Math.max(maxGain(node.left), 0);
        int rightGain = Math.max(maxGain(node.right), 0);
        // 当前节点作为拐点时的路径和
        int priceNewPath = node.val + leftGain + rightGain;
        // 更新全局最大路径和
        maxSum = Math.max(maxSum, priceNewPath);
        // 返回节点的最大贡献值
        return node.val + Math.max(leftGain, rightGain);
    }
    
    // 主函数，计算二叉树的最大路径和
    public static int maxPathSum(TreeNode root) {
        maxGain(root);
        return maxSum;
    }
    
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        List<String> tokensList = new ArrayList<>();
        // 按空格读取所有输入数据
        while (scanner.hasNext()) {
            tokensList.add(scanner.next());
        }
        scanner.close();
        String[] tokens = tokensList.toArray(new String[0]);
        TreeNode root = buildTree(tokens);
        System.out.println(maxPathSum(root));
    }
}

C++ 代码

#include <iostream>
#include <sstream>
#include <string>
#include <vector>
#include <queue>
#include <algorithm>
#include <climits>
using namespace std;

// 定义二叉树节点结构体
struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x): val(x), left(nullptr), right(nullptr) {}
};

// 根据层次遍历结果构造二叉树
TreeNode* buildTree(const vector<string>& tokens) {
    if (tokens.empty() || tokens[0] == "null")
        return nullptr;
    
    TreeNode* root = new TreeNode(stoi(tokens[0]));
    queue<TreeNode*> q;
    q.push(root);
    int i = 1;
    while (i < tokens.size()) {
        TreeNode* current = q.front();
        q.pop();
        // 构造左子节点
        if (i < tokens.size() && tokens[i] != "null") {
            current->left = new TreeNode(stoi(tokens[i]));
            q.push(current->left);
        }
        i++;
        // 构造右子节点
        if (i < tokens.size() && tokens[i] != "null") {
            current->right = new TreeNode(stoi(tokens[i]));
            q.push(current->right);
        }
        i++;
    }
    return root;
}

// 全局变量，记录最大路径和
int maxSum = INT_MIN;

// 递归计算从当前节点出发的最大贡献值
int maxGain(TreeNode* node) {
    if (node == nullptr)
        return 0;
    // 计算左、右子树的最大贡献值，若为负则取0
    int leftGain = max(maxGain(node->left), 0);
    int rightGain = max(maxGain(node->right), 0);
    // 当前节点作为拐点时的路径和
    int priceNewPath = node->val + leftGain + rightGain;
    // 更新全局最大路径和
    maxSum = max(maxSum, priceNewPath);
    // 返回节点的最大贡献值给父节点
    return node->val + max(leftGain, rightGain);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    string input;
    getline(cin, input);
    istringstream iss(input);
    vector<string> tokens;
    string token;
    while (iss >> token) {
        tokens.push_back(token);
    }
    
    TreeNode* root = buildTree(tokens);
    maxGain(root);
    cout << maxSum;
    
    return 0;
}

Leetcode 50.二叉树中的最大路径和-原题链接

题目内容

二叉树中的 路径 被定义为一条节点序列，序列中每对相邻节点之间都存在一条边。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个节点，且不一定经过根节点。

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

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

输入描述

一行包含二叉树的序列化数组，节点值之间用空格隔开，空节点用null表示。

输出描述

一个整数，表示最大路径和。

样例1

输入

1 2 3

输出

6

说明

最优路径是$2 -> 1 -> 3$ ，路径和为 $2 + 1 + 3 = 6$

样例2

输入

-10 9 20 null null 15 7

输出

42

说明

最优路径是$15 -> 20 -> 7$ ，路径和为 $15 + 20 + 7 = 42$

提示

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