This article is participating in Python Theme Month. See the link to the event for more details
Topic describes
This is the second smallest node in the 671. Binary tree on LeetCode, and the difficulty is easy.
Tag: “binary tree”, “tree traversal”, “recursive”
Given a non-null special binary tree, each node is a positive number, and each node can only have two or zero children. If a node has two children, the value of that node is equal to the smaller of the two children.
More formally, root.val = min(root.left.val, root.right.val) always holds.
Given a binary tree like this, you need to print the second smallest value of all the nodes. If the second smallest value does not exist, the output is -1.
Example 1:
Input: root = [2,2,5, NULL, NULL,5,7] Output: 5 Explanation: The smallest value is 2, and the second smallest value is 5.Copy the codeExample 2:
Input: root = [2,2,2] Output: -1 Explanation: The minimum value is 2, but there is no second smallest value.Copy the codeTip:
- The number of nodes in the tree is within [1,25][1, 25][1,25]
<= Node.val <=
– 1- Val == min(root.left.val, root.right.val) for each node in the tree
Tree traversal
A simple way to do this is to walk directly through the tree (breadth & depth) and use HashSet for storage to get the size of all the nodes that have been deduplicated.
Then there are many ways to find the minor value: you can find the minor value by sorting, the complexity is O(nlogn)O(n\log{n})O(nlogn); You can also use the classic two-variable & one traversal method to find the sub-smallest value with complexity O(n)O(n)O(n).
Java code:
class Solution {
Set<Integer> set = new HashSet<>();
public int findSecondMinimumValue(TreeNode root) {
dfs(root);
if (set.size() < 2) return -1;
int first = Integer.MAX_VALUE, second = Integer.MAX_VALUE;
for (int i : set) {
if (i <= first) {
second = first;
first = i;
} else if(i <= second) { second = i; }}return second;
}
void dfs(TreeNode root) {
if (root == null) return; set.add(root.val); dfs(root.left); dfs(root.right); }}Copy the codeclass Solution {
Set<Integer> set = new HashSet<>();
public int findSecondMinimumValue(TreeNode root) {
bfs(root);
if (set.size() < 2) return -1;
int first = Integer.MAX_VALUE, second = Integer.MAX_VALUE;
for (int i : set) {
if (i <= first) {
second = first;
first = i;
} else if(i <= second) { second = i; }}return second;
}
void bfs(TreeNode root) {
Deque<TreeNode> d = new ArrayDeque<>();
d.addLast(root);
while(! d.isEmpty()) { TreeNode poll = d.pollFirst(); set.add(poll.val);if(poll.left ! =null) d.addLast(poll.left);
if(poll.right ! =null) d.addLast(poll.right); }}}Copy the codePython 3 code:
class Solution:
hashset = set(a)def findSecondMinimumValue(self, root: TreeNode) - >int:
self.hashset = set()
self.dfs(root)
if len(self.hashset) < 2:
return -1
first = second = inf
for i in self.hashset:
if i <= first:
second = first
first = i
elif i <= second:
second = i
return second
def dfs(self, root) :
if not root:
return
self.hashset.add(root.val)
self.dfs(root.left)
self.dfs(root.right)
Copy the codeclass Solution:
hashset = set(a)def findSecondMinimumValue(self, root: TreeNode) - >int:
self.hashset = set()
self.bfs(root)
if len(self.hashset) < 2:
return -1
first = second = inf
for i in self.hashset:
if i <= first:
second = first
first = i
elif i <= second:
second = i
return second
def bfs(self, root) :
d = deque([root])
while d:
poll = d.popleft()
self.hashset.add(poll.val)
if poll.left:
d.append(poll.left)
d.append(poll.right)
Copy the code- Time complexity: the searching complexity of the tree is O(n)O(n)O(n) O(n), and the searching complexity is O(n)O(n)O(n) O(n). The overall complexity is O(n)O(n)O(n)
- Space complexity: O(n)O(n)O(n)
recursive
Val = min(root.left.val, root.right.val)) and the number of each child node is either 0 or 2.
We can design the following recursive function, meaning to search from the root of the tree, find the minimum value greater than cur. We then use the global variable ans to store the answer.
void dfs(TreeNode root, int cur)
Copy the codeVal = min(root.left.val, root.right.val), that is, the minimum value will be passed upward, and the final root node must be the global minimum value.
Then, in combination with the statement “the number of children is either 0 or 2”, we can determine whether ans is the first value assigned. If ans is assigned a new value or updated with a smaller ANS, we do not need to search further.
Java code:
class Solution {
int ans = -1;
public int findSecondMinimumValue(TreeNode root) {
dfs(root, root.val);
return ans;
}
void dfs(TreeNode root, int cur) {
if (root == null) return ;
if(root.val ! = cur) {if (ans == -1) ans = root.val;
else ans = Math.min(ans, root.val);
return; } dfs(root.left, cur); dfs(root.right, cur); }}Copy the codePython 3 code:
class Solution:
ans = -1
def findSecondMinimumValue(self, root: TreeNode) - >int:
self.ans = -1
self.dfs(root, root.val)
return self.ans
def dfs(self, root, cur) :
if not root:
return
ifroot.val ! = cur:if self.ans == -1:
self.ans = root.val
else:
self.ans = min(self.ans, root.val)
return
self.dfs(root.left, cur)
self.dfs(root.right, cur)
Copy the code- Time complexity: O(n)O(n)O(n)
- Space complexity: Ignore the space overhead of recursion. It’s O(1)O(1)O(1)
The last
This is article No.671 in our “Brush through LeetCode” series, which began on 2021/01/01. As of the start date, there are 1916 questions on LeetCode, some with locks, and we will first brush through all the questions without locks.
In this series of articles, in addition to explaining how to solve the problem, I’ll give you the most concise code possible. If the general solution is involved, the corresponding code template will be provided.
In order to facilitate the students to debug and submit the code on the computer, I set up a related warehouse: github.com/SharingSour… .
In the repository address, you can see the solution to the series, the corresponding code to the series, the LeetCode link, and other preferred solutions to the series.