#P4067. 二叉树中的最大路径和
-
ID: 2308
Tried: 81
Accepted: 18
Difficulty: 6
二叉树中的最大路径和
题目内容
二叉树中的 路径 被定义为一条节点序列，序列中每对相邻节点之间都存在一条边。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个节点，且不一定经过根节点。
路径和是路径中各节点值的总和。
给你一个二叉树的根节点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∗104]
- −1000<=Node.val<=1000
二叉树最大路径和题解
题解思路
我们可以使用深度优先搜索（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;
}