KK's blog

每天积累多一些

0%

LeetCode 124 Binary Tree Maximum Path Sum

Posted on Edited on Disqus:

LeetCode 124 Binary Tree Maximum Path Sum

Given a binary tree, find the maximum path sum.

For this problem, a path is defined as any sequence of nodes from some starting node to any node in the tree along the parent-child connections. The path must contain at least one node and does not need to go through the root.

For example:
Given the below binary tree,

       
       1
      / \
     2   3

Return 6.

题目大意：

给定一棵二叉树，寻找最大路径和。路径指的是从任意起始节点出发沿着父亲-孩子链接到达某个终止节点的节点序列。路径不一定要穿过根节点。

DFS解题思路(推荐)：

DFS搜索，二叉树的题。步骤主要是考虑

  1. 空指针
  2. 一个node情况或多个node情况（可合并）
    多个node情况下（比如3个节点），有4种情况下含根节点的和：左子树+根节点，右子树+跟节点，根节点，左子树+根节点+右子树。这些情况包含了所有可能的和的情况。但值得注意的是，前三种
    情况可以是子问题的解，也就是它返回值将成为此根节点父亲的左或右子树的解，但第四种情况例外，因为此情况形成的路径与根节点父亲并不在一条路径上。所以此情况应在全局变量中比较
    并不能作为返回值。
    gmax = max {return max{val,left+val,right+val} or left+val+right}

注意事项：

  1. 4种情况: root， root + left, root + right, left + root + right, 不要漏掉最后一种left_sum + root.val + right_sum
  2. 全局最大值作为返回值，初始值为负无穷float(‘-inf’)。

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
def maxPathSum(self, root: TreeNode) -> int:
	_, path_gsum = self.dfs(root)
	return path_gsum

def dfs(self, root: TreeNode) -> int:
	if not root:
       return float('-inf'), float('-inf')
	left_sum, left_gsum = self.dfs(root.left)
	right_sum, right_gsum = self.dfs(root.right)
	max_path_sum = max(left_sum + root.val, right_sum + root.val, root.val)
	max_path_gsum = max(max_path_sum, left_gsum, right_gsum, left_sum + root.val + right_sum)
	return max_path_sum, max_path_gsum

算法II迭代解题思路：

由上述算法看出，属于后序遍历，因为先left, right, 再计算root。所以用后序遍历模板。然后定义dp[root]为以root为结束点的最大路径值，这与上题也一样。
递归式为

1
dp[node] = max(dp[node.left] + node.val, dp[node.right] + node.val, node.val)

res为全局最大值，也和上述一致
max_path_sum = dp[node]
res = left_gsum, right_gsum

注意事项：

  1. occurrence先加再比较

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def maxPathSum2(self, root: TreeNode) -> int:
	it, stack, res = root, [], float('-inf')
	dp = collections.defaultdict(int)
	while it:
		stack.append((it, 0))
		it = it.left

	while stack:
		node, occurrence = stack.pop()
		occurrence += 1 # remember
		if occurrence == 2:
			dp[node] = max(dp[node.left] + node.val, dp[node.right] + node.val, node.val)
			res = max(res, dp[node], dp[node.left] + node.val + dp[node.right])
			continue
		else:
			stack.append((node, occurrence))
		if node.right:
			n = node.right
			while n:
				stack.append((n, 0))
				n = n.left
	return res

Follow-up

若path的起始点均为叶子节点

解题思路：

叶子节点要返回值，gsum为无穷小。修改max_path_sum和max_path_gsum公式，不含单独root以及gsum不含以root为终点的路径。
还有路径可能不存在

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def maxPathSum_fromleaf2leaf(self, root: TreeNode) -> int:
	path_sum, path_gsum = self.dfs_leaf(root)
	return path_gsum if path_gsum != float('-inf') else None

def dfs_leaf(self, root: TreeNode) -> int:
	if not root:
		return float('-inf'), float('-inf')
	if not root.left and not root.right:
		return root.val, float('-inf') # remember no gsum
	left_sum, left_gsum = self.dfs_leaf(root.left)
	right_sum, right_gsum = self.dfs_leaf(root.right)
	max_path_sum = max(left_sum + root.val, right_sum + root.val)
	max_path_gsum = max(left_gsum, right_gsum, left_sum + root.val + right_sum)
	return max_path_sum, max_path_gsum

Follow-up 2

若path的起始点均为叶子节点且只能从某些特定的叶子节点出发和结束

解题思路：

同上，只不过加入条件root.val in endnodes

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def maxPathSum_fromSpecificNodes(self, root: TreeNode, endnodes) -> int:
	path_sum, path_gsum = self.dfs_end_nodes(root, set(endnodes))
	return path_gsum if path_gsum != float('-inf') else None

def dfs_end_nodes(self, root: TreeNode, endnodes) -> int:
	if not root:
		return float('-inf'), float('-inf')
	if not root.left and not root.right and root.val in endnodes:
		return root.val, float('-inf') # remember no gsum
	left_sum, left_gsum = self.dfs_end_nodes(root.left, endnodes)
	right_sum, right_gsum = self.dfs_end_nodes(root.right, endnodes)
	max_path_sum = max(left_sum + root.val, right_sum + root.val)
	max_path_gsum = max(left_gsum, right_gsum, left_sum + root.val + right_sum)
	return max_path_sum, max_path_gsum

Follow-up 3

若path的起始点可为任意节点且只能从某些特定的叶子节点出发和结束

解题思路：

若起始节点为非叶子节点，注意将表达式修改为原始表达式。

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def maxPathSum_fromSpecificNodes2(self, root: TreeNode, endnodes) -> int:
	path_sum, path_gsum = self.dfs_end_nodes2(root, set(endnodes))
	return path_gsum if path_gsum != float('-inf') else None

def dfs_end_nodes2(self, root: TreeNode, endnodes) -> int:
	if not root:
		return float('-inf'), float('-inf')
	if not root.left and not root.right and root.val in endnodes:
		return root.val, float('-inf') # remember no gsum
	left_sum, left_gsum = self.dfs_end_nodes2(root.left, endnodes)
	right_sum, right_gsum = self.dfs_end_nodes2(root.right, endnodes)
	max_path_sum = max(left_sum + root.val, right_sum + root.val)
	if root.val in endnodes:
		max_path_sum = max(max_path_sum, root.val)
	max_path_gsum = max(left_gsum, right_gsum, left_sum + root.val + right_sum)
	if root.val in endnodes:
		max_path_gsum = max(max_path_gsum, max_path_sum)
	return max_path_sum, max_path_gsum

注意事项：

  1. 4种情况
  2. 定义全局变量来比较最大值，因为左到右情况不能返回。全局变量初始值为负无穷。

Java代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int gsum = Integer.MIN_VALUE;
public int maxPathSum(TreeNode root){
	gsum = 0;
	int a = max(root);
	return gsum;
}
public int max(TreeNode root){
	if(root==null)
		return 0;
	int lmax = max(root.left);
	int rmax = max(root.right);
	int sum = Math.max(Math.max(lmax, rmax)+root.val,root.val);
	gsum = Math.max(Math.max(gsum, sum), lmax+root.val+rmax);
	return sum;
}

算法分析：

两种方法时间复杂度为O(n)，n为节点数。空间复杂度为O(h)，h为二叉树高度。

相关题目：

LeetCode 112 Path Sum
LeetCode 124 Binary Tree Maximum Path Sum

Free mock interview