KK's blog

LeetCode

<div>

Given a binary tree root, a node X in the tree is named good if in the path from root to X there are no nodes with a value greater than X.

Return the number of good nodes in the binary tree.

Example 1:

<pre>Input: root = [3,1,4,3,null,1,5] Output: 4 Explanation: Nodes in blue are good. Root Node (3) is always a good node. Node 4 -> (3,4) is the maximum value in the path starting from the root. Node 5 -> (3,4,5) is the maximum value in the path Node 3 -> (3,1,3) is the maximum value in the path.</pre>

Example 2:

<pre>Input: root = [3,3,null,4,2] Output: 3 Explanation: Node 2 -> (3, 3, 2) is not good, because "3" is higher than it.</pre>

Example 3:

<pre>Input: root = [1] Output: 1 Explanation: Root is considered as good.</pre>

Constraints:

• The number of nodes in the binary tree is in the range [1, 10^5].
• Each node's value is between [-10^4, 10^4].

</div>

题目大意：

一个节点是good表示该节点从root到自己的路径上，所有节点都小于等于自己。求二叉树的good节点个数

解题思路：

统计左右子树的good节点个数，最重要是引入类似于min, max验证BST，引入path_max来记录路径上的最大值，只要该节点值大于path_max就是good节点。DFS返回good节点个数

解题步骤：

N/A

注意事项：

1. 引入path_max来记录路径上的最大值

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12

def goodNodes(self, root: TreeNode) -> int:
	return self.dfs(root, float('-inf'))

def dfs(self, root, path_max):
	if not root:
		return 0
	left = self.dfs(root.left, max(root.val, path_max))
	right = self.dfs(root.right, max(root.val, path_max))
	res = left + right
	if path_max <= root.val:
		res += 1
	return res

算法分析：

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

LeetCode

<div>

Given a root of an N-ary tree, you need to compute the length of the diameter of the tree.

The diameter of an N-ary tree is the length of the longest path between any two nodes in the tree. This path may or may not pass through the root.

(Nary-Tree input serialization is represented in their level order traversal, each group of children is separated by the null value.)

Example 1:

<pre>Input: root = [1,null,3,2,4,null,5,6] Output: 3 Explanation: Diameter is shown in red color.</pre>

Example 2:

<pre>Input: root = [1,null,2,null,3,4,null,5,null,6] Output: 4 </pre>

Example 3:

<pre>Input: root = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14] Output: 7 </pre>

Constraints:

• The depth of the n-ary tree is less than or equal to 1000.
• The total number of nodes is between [1, 10<sup>4</sup>].

</div>

题目大意：

求树的直径：任何两个节点的最大距离

解题思路：

类似于LeetCode 543 Diameter of Binary Tree，但此题为N叉树

解题步骤：

DFS

注意事项：

1. 求数组中最大的两数和，用去掉最大值的方法得到次大值。还要注意初始值加入[1, 1]，避免没有儿子节点或只有一个的情况

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

def diameter(self, root: 'Node') -> int:
	max_len = 0

	def dfs(root):
		if not root:
			return 0
		nonlocal max_len
		path_len = [1, 1]
		for child in root.children:
			path_len.append(dfs(child) + 1)
		largest = max(path_len)
		path_len.remove(largest)
		second_largest = max(path_len)
		total = largest + second_largest - 1
		max_len = max(total, max_len)
		return largest

	dfs(root)
	return max_len - 1

算法分析：

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

LeetCode

<div>

A string s is called good if there are no two different characters in s that have the same frequency.

Given a string s, return the minimum number of characters you need to delete to make s good.

The frequency of a character in a string is the number of times it appears in the string. For example, in the string "aab", the frequency of 'a' is 2, while the frequency of 'b' is 1.

Example 1:

<pre>Input: s = "aab" Output: 0 Explanation: s is already good. </pre>

Example 2:

<pre>Input: s = "aaabbbcc" Output: 2 Explanation: You can delete two 'b's resulting in the good string "aaabcc". Another way it to delete one 'b' and one 'c' resulting in the good string "aaabbc".</pre>

Example 3:

<pre>Input: s = "ceabaacb" Output: 2 Explanation: You can delete both 'c's resulting in the good string "eabaab". Note that we only care about characters that are still in the string at the end (i.e. frequency of 0 is ignored). </pre>

Constraints:

• 1 <= s.length <= 10<sup>5</sup>
• s contains only lowercase English letters.

</div>

题目大意：

给定一个字符串，求最小删除次数使得字符串的每一种字符频率不同

解题思路：

按题意求解，若遇到频率相同的字符，就将其减一，也就是删除一个字符，使得它不再与其他字符频率相同直到0. 关键在用一个unique_count的set来记录频数

解题步骤：

N/A

注意事项：

1. 用一个unique_count的set来记录频数

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12

def minDeletions(self, s: str) -> int:
	char_to_count = collections.Counter(s)
	unique_count = set()
	res = 0
	for char, count in char_to_count.items():
		cur_count = count
		while cur_count in unique_count:
			cur_count -= 1
			res += 1
		if cur_count > 0:
			unique_count.add(cur_count)
	return res

算法分析：

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

LeetCode

<div>

Given the root of a binary tree, return the length of the longest consecutive sequence path.

The path refers to any sequence of nodes from some starting node to any node in the tree along the parent-child connections. The longest consecutive path needs to be from parent to child (cannot be the reverse).

Example 1:

<pre>Input: root = [1,null,3,2,4,null,null,null,5] Output: 3 Explanation: Longest consecutive sequence path is 3-4-5, so return 3. </pre>

Example 2:

<pre>Input: root = [2,null,3,2,null,1] Output: 2 Explanation: Longest consecutive sequence path is 2-3, not 3-2-1, so return 2. </pre>

Constraints:

• The number of nodes in the tree is in the range [1, 3 * 10<sup>4</sup>].
• -3 * 10<sup>4</sup> <= Node.val <= 3 * 10<sup>4</sup>

</div>

题目大意：

求从父到子的最长连续数列的长度(由小到大)

解题思路：

DFS

LeetCode 298 Binary Tree Longest Consecutive Sequence 父亲到儿子由小到大 LeetCode 549 Binary Tree Longest Consecutive Sequence II 任一节点到另一个节点由小到大

解题步骤：

N/A

注意事项：

1. 题意是从父到儿子的有小到大数列，而不是儿子到父亲
2. 以root为起点的最长数列，若root不符合条件，不加入left或right的长度
3. 类似于LeetCode 124 Binary Tree Maximum Path Sum，有三种情况：自己，自己+左，自己+右

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

def longestConsecutive(self, root: TreeNode) -> int:
	max_len = 0

	def dfs(root):
		if not root:
			return 0
		nonlocal max_len
		lpath = rpath = 1
		left = dfs(root.left)
		right = dfs(root.right)
		if root.left and root.val + 1 == root.left.val:  # remember not ==
			lpath += left
		if root.right and root.val + 1 == root.right.val:
			rpath += right
		res = max(lpath, rpath)
		max_len = max(res, max_len)
		return res

	dfs(root)
	return max_len

算法分析：

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

LeetCode

<div>

Given the root of a binary tree, return the length of the longest consecutive path in the tree.

A consecutive path is a path where the values of the consecutive nodes in the path differ by one. This path can be either increasing or decreasing.

• For example, [1,2,3,4] and [4,3,2,1] are both considered valid, but the path [1,2,4,3] is not valid.

On the other hand, the path can be in the child-Parent-child order, where not necessarily be parent-child order.

Example 1:

<pre>Input: root = [1,2,3] Output: 2 Explanation: The longest consecutive path is [1, 2] or [2, 1]. </pre>

Example 2:

<pre>Input: root = [2,1,3] Output: 3 Explanation: The longest consecutive path is [1, 2, 3] or [3, 2, 1]. </pre>

Constraints:

• The number of nodes in the tree is in the range [1, 3 * 10<sup>4</sup>].
• -3 * 10<sup>4</sup> <= Node.val <= 3 * 10<sup>4</sup>

</div>

题目大意：

求任意节点到另一个节点的最长连续数列的长度(由小到大)

解题思路：

类似于LeetCode 298 Binary Tree Longest Consecutive Sequence，不过由于父亲到儿子可能递增或递减，所以DFS返回值也返回递增和递减的长度

LeetCode 298 Binary Tree Longest Consecutive Sequence 父亲到儿子由小到大 LeetCode 549 Binary Tree Longest Consecutive Sequence II 任一节点到另一个节点由小到大

类似于LeetCode 124 Binary Tree Maximum Path Sum，有四种情况：自己，自己+左，自己+右，左+右

解题步骤：

N/A

注意事项：

1. DFS返回值也返回递增和递减的长度
2. 类似于LeetCode 124 Binary Tree Maximum Path Sum，有四种情况：自己，自己+左，自己+右，左+右

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

def longestConsecutive(self, root: TreeNode) -> int:
	max_len = 0

	def dfs(root):
		if not root:
			return 0, 0  # (increasing, decreasing) from root
		nonlocal max_len
		inc = desc = 1
		lpath = rpath = 1
		left = dfs(root.left)
		right = dfs(root.right)
		if root.left and root.val + 1 == root.left.val:
			lpath += left[0]
		if root.right and root.val + 1 == root.right.val:
			rpath += right[0]
		inc = max(1, lpath, rpath)

		lpath = rpath = 1
		if root.left and root.val - 1 == root.left.val:
			lpath += left[1]
		if root.right and root.val - 1 == root.right.val:
			rpath += right[1]
		desc = max(1, lpath, rpath)

		total = inc + desc - 1
		max_len = max(inc, desc, total, max_len)
		return inc, desc

	dfs(root)
	return max_len

算法分析：

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