KK's blog

每天积累多一些

0%

Posted on Edited on Disqus:

LeetCode



Design a data structure to store the strings’ count with the ability to return the strings with minimum and maximum counts.

Implement the AllOne class:

AllOne() Initializes the object of the data structure. inc(String key) Increments the count of the string key by 1. If key does not exist in the data structure, insert it with count 1.
dec(String key) Decrements the count of the string key by 1. If the count of key is 0 after the decrement, remove it from the data structure. It is guaranteed that key exists in the data structure before the decrement. getMaxKey() Returns one of the keys with the maximal count. If no element exists, return an empty string "".
getMinKey() Returns one of the keys with the minimum count. If no element exists, return an empty string "".

Example 1:

Input
[“AllOne”, “inc”, “inc”, “getMaxKey”, “getMinKey”, “inc”, “getMaxKey”, “getMinKey”]
[[], [“hello”], [“hello”], [], [], [“leet”], [], []]
Output
[null, null, null, “hello”, “hello”, null, “hello”, “leet”]

Explanation
AllOne allOne = new AllOne();
allOne.inc(“hello”);
allOne.inc(“hello”);
allOne.getMaxKey(); // return “hello”
allOne.getMinKey(); // return “hello”
allOne.inc(“leet”);
allOne.getMaxKey(); // return “hello”
allOne.getMinKey(); // return “leet”


Constraints: 1 <= key.length <= 10
key consists of lowercase English letters. It is guaranteed that for each call to dec, key is existing in the data structure.
At most `5 104calls will be made toinc,dec,getMaxKey, andgetMinKey`.

题目大意：

设计数据结构，使其支持增加或减少一个单词的频数，最大或最小单词的频数。注意最小频数不能为0

解题思路：

这个频数有点似LRU的分层思路，加入self.max_freq, 其他操作都可以实现，但是dec操作不能达到O(1), 因为若某个最小频数单词从1变成0，需要检索频率到下一个有节点的层。
改进就是要将频率的的值连起来，所以参考LRU，map的key是频率，value是node，node中含有freq，形成一个环。而node含有该频率对应的单词set，inc/dec就是将单词移动另一个node中

解题步骤：

N/A

注意事项：

  1. 与LRU区别: map的key是频率，node含有频率和单词set，数据结构加入key_to_count。LL是从最大频率到最小频率
  2. inc操作将节点从原频率node移到下一个频率node，若新node不存在，调用append_before. 然后从原频率node的单词set中删除该单词，若set为空，删除此node以及map中的entry
  3. dec与inc类似，但要注意频率变成0的情况：不移到新的node，且从key_to_count中删除该单词

Python代码：

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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
class AllOne(TestCases):

    def __init__(self):
        self.freq_to_node = {}
        self.head = ListNode(0)
        self.tail = ListNode(0)
        self.head.next, self.tail.prev = self.tail, self.head
        self.key_to_count = collections.defaultdict(int)

    def inc(self, key: str) -> None:
        count = self.key_to_count[key]
        old_node = self.freq_to_node[count] if count in self.freq_to_node else self.tail
        count += 1
        if count not in self.freq_to_node:
            self.freq_to_node[count] = self.append_before(old_node)
        new_node = self.freq_to_node[count]
        new_node.key_set.add(key)
        self.key_to_count[key] = count

        count -= 1
        if count in self.freq_to_node and key in self.freq_to_node[count].key_set:
            self.freq_to_node[count].key_set.remove(key)
            if len(self.freq_to_node[count].key_set) == 0:
                self.remove_node(self.freq_to_node[count])
                self.freq_to_node.pop(count) # remember

    def dec(self, key: str) -> None:
        count = self.key_to_count[key]
        old_node = self.freq_to_node[count] if count in self.freq_to_node else self.head
        count -= 1
        if count > 0: # remember
            if count not in self.freq_to_node:
                self.freq_to_node[count] = self.append_after(old_node)
            new_node = self.freq_to_node[count]
            new_node.key_set.add(key)
            self.key_to_count[key] = count
        else:
            self.key_to_count.pop(key)

        count += 1
        if count in self.freq_to_node and key in self.freq_to_node[count].key_set:
            self.freq_to_node[count].key_set.remove(key)
            if len(self.freq_to_node[count].key_set) == 0:
                self.remove_node(self.freq_to_node[count])
                self.freq_to_node.pop(count)

    def getMaxKey(self) -> str:
        node = self.head.next
        return '' if node == self.tail else next(iter(node.key_set))

    def getMinKey(self) -> str:
        node = self.tail.prev
        return '' if node == self.head else next(iter(node.key_set))

    def append_before(self, node):
        new_node = ListNode(node.freq + 1)
        predecessor, successor = node.prev, node
        predecessor.next, new_node.prev = new_node, predecessor
        new_node.next, successor.prev = successor, new_node
        return new_node

    def append_after(self, node):
        new_node = ListNode(node.freq - 1)
        predecessor, successor = node, node.next
        predecessor.next, new_node.prev = new_node, predecessor
        new_node.next, successor.prev = successor, new_node
        return new_node

    def remove_node(self, node):
        predecessor, successor = node.prev, node.next
        predecessor.next, successor.prev = successor, predecessor
        node.prev, node.next = None, None


class ListNode:
    def __init__(self, freq=0, next=None, prev=None):
        self.key_set = set()
        self.freq = freq
        self.next = next
        self.prev = prev

算法分析：

时间复杂度为O(1)，空间复杂度O(n)

Posted on Edited on Disqus:
  • 典型递归式
  • 单序列或匹配型DP模板
  • 数值到个数DP模板(最常考)
  • 区间型DP模板
  • 压缩空间
  • 打印路径

典型递归式：

单序列型(与一个或多个前状态有关)
硬币个数(数值型)： dp[i] = min(dp[i], dp[i - j] + 1)
偷房子： dp[i] = max(dp[i-1], dp[i-2] + nums[i - 1])
LIS： dp[i] = max(dp[i], dp[j] + 1) 1 <= j < i
Work break： dp[i] |= dp[j] and s[j:i] in word_set, 0 <= j < i

坐标型DP(与上、左等两个前状态有关)

1
dp[n][m] = max{1, min(dp[n+1][m], dp[n][m+1]) - dungeon[n][m]}

匹配型(与上、左、左上等三个前状态有关)

1
2
正则： dp[i][j] = dp[i-1][j-1] && (p[j-1] == . || s[i-1] == p[j-1])
OR ((dp[i-1][j] && (s[i-1] == p[j-2] || p[j-2] == .)) || dp[i][j-2]) && p[j-1] == *

区间型(与该区间内以k为划分的两个子区间有关)

1
dp[i][j] = max{dp[i][m] + nums[i]×nums[m]×nums[j] + dp[m][j]}, i < m < j

多状态型DP(DP有多个终止状态)

1
2
3
4
5
dp = dp     if s[i] = '0'
   = dp + 1 if s[i] = '1'
   
dp2 = min(dp2 + 1, dp + 1)     if s[i] = '0'
    = min(dp2, dp)             if s[i] = '1'

解题步骤：

DP五部曲

  1. [初始化]dp数组n+1
  2. dp初始值也就是基本条件
  3. [实现]定义状态和递归式
  4. [答案] 如dp[-1]
  5. [优化]是否可以用滚动内存优化空间

单序列或匹配型DP模板

实现注意事项(5点)：

  1. [多1][初始化]初始化矩阵，dp是原长度加1。因为令边界计算方便. 遍历从多少开始，取决于前状态多少个，若递归式含dp[i-1],从1开始，如果dp[i-2]就从2开始.数值型DP，如硬币个数DP长度是数值amount，不是数组长度。Python用dp = [[0 for _ in range(M)] for _ in range(N)], M为col数，再row数
  2. [特殊初始值]是第一步的完善，若一维初始化dp0，若为矩阵，初始化dp[0][0]以及上和左边界。求个数dp[0] = 1, 求最值, dp[0] = 0因为递归式含+1
  3. [多1]跳过初始值，i从1循环到len(dp)而不是len(s), 因为用了dp[0]占位。若不用占位法，就要用if语句判断第一位的边界。大部分递归式含i-1项，所以绝大部分从1开始，从什么开始取决于递归式，这也受第二步的影响
  4. [少1]用到原数组s时候是s[i - 1]而不是s[i], 因为用了dp[0]占位。实现时候递归式和条件要合法，保证边界内，如dp[i - t] => i - t >=0和s[i - 1 - dp[i - 1] - 1]，见最长括号数
  5. [答案]不一定是dp[-1]，如果以某位结束的答案而不是累积结果，一般就用max_len

累积DP递归公式

1
dp[n] = max(dp[n - 1], f)

Python代码：

1
2
3
4
5
6
def dp(self, s):
	dp = [False] * (len(s) + 1)
	dp[0] = True
	for i in range(1, len(dp)):
		...dp[i]...s[i-1]
	return dp[-1]

算法分析：

时间复杂度为O(n)，空间复杂度O(n)。

应用题型：

LeetCode 139 Word Break
LeetCode 044 Wildcard Matching
LeetCode 010 Regular Expression Matching

数值到个数DP模板(最常考)

求个数DP是比较简单的DP，但也是比较常考的。一般DP是前n个，这里是用数值，这点还是有点难的。

递归公式

1
dp[n + num[i]] = dp[n], n = [1, tgt], i = [0, len(nums) - 1]

注意事项：

  1. dp[i + nums[j]] += dp[i] 而不是dp[i] + 1
  2. dp[0] = 1表示数值为0，可以不用任何数就能获得，所以是1种
  3. i从0开始，因为此题递归式用相加i + nums[j]，而不是相减
  4. nums先排序，否则如[3, 1, 2, 4]，返回dp[1] = 0, 但应该是dp[1] = 1
  5. 上述4点注意事项只有1和2。数
1
2
3
4
5
6
7
8
9
10
def dp(self, nums, target):
	nums.sort() # remember
	dp = [0] * (target + 1)
	dp[0] = 1 # remember
	for i in range(len(dp)):
		for j in range(len(nums)):
			if i + nums[j] > target:
				break
			dp[i + nums[j]] += dp[i] # remember no +1
	return dp[-1]

应用题型：

LeetCode 377 Combination Sum IV
LeetCode 198 House Robber

一个变体是求最小个数

递归公式

1
dp[n + coins[i]] = min{dp[n + coins[i]], dp[n] + 1}, n = [1, tgt], i = [0, len(nums) - 1]

不同之处：

  1. 递归式是dp[i] + 1
  2. dp初始值为最大值，而且dp[0] = 0
1
2
3
4
5
6
7
8
9
10
def dp(self, coins: List[int], amount: int) -> int:
	coins.sort()
	dp = [float('inf')] * (amount + 1)
	dp[0] = 0
	for i in range(len(dp)):
		for j in range(len(coins)):
			if i + coins[j] > amount:
				break
			dp[i + coins[j]] = min(dp[i + coins[j]], dp[i] + 1)
	return dp[-1] if dp[-1] < float('inf') else -1  # remember

应用题型：

LeetCode 322 Coin Change
LeetCode 871 Minimum Number of Refueling Stops

算法分析：

时间复杂度为O(n*target)，空间复杂度O(n)。

区间型DP模板

k循环从1还是从2开始取决于递归式

1
2
3
4
5
6
7
def dp(self, s: str) -> int:
	# init dp array
	for k in range(1, len(s)):
		for i in range(len(s) - k):
			j = i + k
			# dp formula
	return dp[0][-1]

应用题型：

LeetCode 516 Longest Palindromic Subsequence
LeetCode 312 Burst Balloons

压缩空间

若递归式和上一行有关，绝大部分属于此情况，就可以用两行，原数量列来处理

与标准模板不同之处：

  1. 行个数为2
  2. i仍然是遍历到所有行，所以不能用len(dp),而是len(text1) + 1.
  3. dp行不用i，而是i % 2
1
2
3
4
5
6
7
8
9
def longestCommonContinuous(self, text1: str, text2: str) -> int:
	dp = [[0 for _ in range(len(text2) + 1)] for _ in range(2)]
	res = 0
	for i in range(1, len(text1) + 1):
		for j in range(1, len(dp[0])):
			if text1[i - 1] == text2[j - 1]:
				dp[i % 2][j] = dp[(i - 1) % 2][j - 1] + 1
				res = max(res, dp[i % 2][j])
	return res

应用题型：

Karat 002 Longest Common Continuous Subarray
LeetCode 063 Unique Paths II

打印路径

三种类型：

  1. LCA: Karat 002 Longest Common Continuous Subarray res = history1[i - dp[i][j]:i]
  2. LIS:
    LeetCode 300 Longest Increasing Subsequence
    LeetCode 368 Largest Divisible Subset
  3. LCS: LeetCode 1143 Longest Common Subsequence

LIS过程：

  1. path跟dp数组一样大，记录回溯跳转j -> i路径path[i - 1] = j - 1
  2. 记录回溯开始点if res == dp[i]: biggest_pos = i - 1
  3. 循环长度为res, 从biggest_pos开始

Python代码：

1
2
3
4
5
6
def print_path(self, nums, path[:biggest_pos + 1], dp_value = res):
	pos, res = len(path) - 1, []
	for _ in range(dp_value):
		res.append(nums[pos])
		pos = path[pos]
	return res[::-1]

LCS:

  1. path和dp一样，不用特别数组
  2. 从右下到左上，若上或左值一样，向此方向移动，直到左和上少一，此时res -= 1

Python代码：

1
2
3
4
5
6
7
8
9
10
11
longest, res = dp[-1][-1], ''
while m >= 0 and n >= 0:
	if dp[m - 1][n] == longest:
		m -= 1
	elif dp[m][n - 1] == longest:
		n -= 1
	else:
		res += text1[m - 1]
		longest -= 1
		m -= 1
		n -= 1

Posted on Edited on Disqus:

LeetCode



Given an integer array nums, return the length of the longest strictly increasing subsequence.

A subsequence is a sequence that can be derived from an array by deleting some or no elements without changing the order of the remaining elements. For example, [3,6,2,7] is a subsequence of the array [0,3,1,6,2,2,7].

Example 1:

Input: nums = [10,9,2,5,3,7,101,18]
Output: 4
Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4.


Example 2:

Input: nums = [0,1,0,3,2,3]
Output: 4


Example 3:

Input: nums = [7,7,7,7,7,7,7]
Output: 1


Constraints:

1 <= nums.length <= 2500 -10<sup>4</sup> <= nums[i] <= 10<sup>4</sup>

Follow up: Can you come up with an algorithm that runs in O(n log(n)) time complexity?

DP算法思路：

N/A

注意事项：

  1. 初始化从1开始，因为一个数是递增序列
  2. 返回值不是dp[-1]，而是所有dp的最大值

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
[3, 5, 1, 3, 9, 5, 6] 1, 3, 5, 6
[1, 0]
dp[i] = max(dp[j]) + 1, if nums[i-1] > nums[j-1], 1 <= j < i
	
def lengthOfLIS(self, nums: List[int]) -> int:
	if not nums:
		return 0
	res = 1
	# dp = [0, 1, 0]
	dp = [1] * (len(nums) + 1)
	for i in range(1, len(dp)):
		# i = 2
		# j = 1
		for j in range(1, i):
			if nums[i - 1] > nums[j - 1]:
				dp[i] = max(dp[i], dp[j] + 1)
		res = max(res, dp[i])
	return res

算法分析：

时间复杂度为O(n2)，空间复杂度O(n2).

打印路径算法思路：

N/A

注意事项：

  1. path数组大小和原数组一样，因为path数组的下标和值都是下标，这样不用-1，直接nums[pos]，不容易错
  2. 多了Line 11 - 12和14 - 15，需要记录产生最大值的下标
  3. 打印的时候path数组的下标和值都是下标，而值是前一个下标，所以是pos = positions[pos]，循环次数为dp值，开始下标为dp值对应的下标path[:biggest_pos + 1]。

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
def lengthOfLIS_with_path(self, nums: List[int]) -> int:
	if not nums:
		return 0
	res, path = 1, [0] * len(nums)  # remember no + 1
	biggest_pos = -1
	dp = [1] * (len(nums) + 1)
	for i in range(1, len(dp)):
		for j in range(1, i):
			if nums[i - 1] > nums[j - 1]:
				dp[i] = max(dp[i], dp[j] + 1)
				if dp[i] == dp[j] + 1:
					path[i - 1] = j - 1
		res = max(res, dp[i])
		if res == dp[i]:
			biggest_pos = i - 1
	path_list = self.print_path(nums, path[:biggest_pos + 1], res)
	return path_list

def print_path(self, nums, path, dp_value):
	pos, res = len(path) - 1, []
	for _ in range(dp_value):
		res.append(nums[pos])
		pos = path[pos]
	return res[::-1]

bisect算法II解题思路：

N/A

注意事项：

  1. bisect_left类似于greater_or_equal_position但若equal时，取第一个，但greater_or_equal_position是取最后一个，此题没关系，因为相等的数会被替换掉，递增序列中不会存在相等的数

Python代码：

1
2
3
4
5
6
7
8
9
10
11
def lengthOfLIS(self, nums: List[int]) -> int:
	if not nums:
		return 0
	res = []
	for i in range(len(nums)):
		pos = bisect.bisect_left(res, nums[i])
		if pos < len(res):
			res[pos] = nums[i]
		else:
			res.append(nums[i])
	return len(res)

算法分析：

时间复杂度为O(nlogn)，空间复杂度O(n).

Posted on Edited on Disqus:

LeetCode



Given two strings text1 and text2, return the length of their longest common subsequence. If there is no common subsequence, return 0.

A subsequence of a string is a new string generated from the original string with some characters (can be none) deleted without changing the relative order of the remaining characters.

For example, "ace" is a subsequence of "abcde".

A common subsequence of two strings is a subsequence that is common to both strings.

Example 1:

Input: text1 = “abcde”, text2 = “ace”
Output: 3
Explanation: The longest common subsequence is “ace” and its length is 3.


Example 2:

Input: text1 = “abc”, text2 = “abc”
Output: 3
Explanation: The longest common subsequence is “abc” and its length is 3.


Example 3:

Input: text1 = “abc”, text2 = “def”
Output: 0
Explanation: There is no such common subsequence, so the result is 0.


Constraints: 1 <= text1.length, text2.length <= 1000
* text1 and text2 consist of only lowercase English characters.

题目大意：

求两字符串的最大公共字符序列，不一定需要连续

解题思路：

两字符串最值问题用DP
dp[i][j]为最大公共字符序列，最后一位不需要相等。递归式为:

1
2
dp[i][j] = dp[i - 1][j - 1] + 1 if text1[i - 1] == text2[j - 1]
         = max(dp[i - 1][j], dp[i][j - 1])

解题步骤：

DP五点注意事项

注意事项：

  1. 不相等时候不需要dp[i - 1][j - 1]，因为已经包含在dp[i - 1][j]或dp[i][j - 1]中, DP属于累计DP

Python代码：

1
2
3
4
5
6
7
8
9
10
11
# dp[i][j] = dp[i - 1][j - 1] + 1 if text1[i - 1] == text2[j - 1]
#          = max(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1])
def longestCommonSubsequence(self, text1: str, text2: str) -> int:
	dp = [[0 for _ in range(len(text2) + 1)] for _ in range(len(text1) + 1)]
	for i in range(1, len(dp)):
		for j in range(1, len(dp[0])):
			if text1[i - 1] == text2[j - 1]:
				dp[i][j] = dp[i - 1][j - 1] + 1
			else:
				dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) # no dp[i - 1][j - 1] but no impact
	return dp[-1][-1]

打印路径

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
longest, res = dp[-1][-1], ''
while m >= 0 and n >= 0:
	if dp[m - 1][n] == longest:
		m -= 1
	elif dp[m][n - 1] == longest:
		n -= 1
	else:
		res += text1[m - 1]
		longest -= 1
		m -= 1
		n -= 1
return res[::-1]

算法分析：

时间复杂度为O(nm)，空间复杂度O(nm)

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