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

题目描述

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

image-20230804231207274

image-20230804231214825

思路分析

我们可以使用递归的方法来解决这个问题。对于每个节点，我们需要计算两件事：

  1. 以该节点为根的最大路径和。
  2. 经过该节点的最大路径和。

具体步骤如下：

  1. 对于每个节点，计算其左子树和右子树的最大贡献值（即从该节点出发到叶子节点的最大路径和）。
  2. 如果左子树或右子树的最大贡献值为负数，则不考虑该子树。
  3. 计算经过该节点的路径和，并更新全局最大路径和。
  4. 返回以该节点为根的最大路径和。

参考代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

func maxPathSum(root *TreeNode) int {
	maxSum := math.MinInt32

	var maxGain func(node *TreeNode) int
	maxGain = func(node *TreeNode) int {
		if node == nil {
			return 0
		}

		// 递归计算左右子树的最大贡献值
		leftGain := max(maxGain(node.Left), 0)
		rightGain := max(maxGain(node.Right), 0)

		// 计算当前节点的最大路径和
		curPathSum := node.Val + leftGain + rightGain

		// 更新全局最大路径和
		maxSum = max(maxSum, curPathSum)

		// 返回当前节点的最大贡献值
		return node.Val + max(leftGain, rightGain)
	}

	maxGain(root)
	return maxSum
}
  • 时间复杂度：O (N)，其中 N 是二叉树中的节点数。每个节点在递归中只被访问一次。
  • 空间复杂度：O (H)，其中 H 是二叉树的高度。递归调用栈的深度等于二叉树的高度。

🍏 点击查看 Java 题解

1

write your code here
本文作者:
本文链接: https://hgnulb.github.io/blog/2023/91304980
版权声明: 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！