Leetcode – 671-the second smallest node in the binary tree

[Blog link]

The way to study ๐Ÿ”

The nuggets home page

[Topic description]

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. Example 2: Input: root = [2,2,2] Output: -1 Description: The minimum value is 2, but there is no second smallest value. Tip: Val <= 231-1 for each Node in the tree root.val == min(root.left.val, Root.right.val) Related Topics tree deep-first search binary tree ๐Ÿ‘ 159 ๐Ÿ‘Ž 0Copy the code

[Topic link]

Leetcode title link

[making address]

Code link

[ๆ€่ทฏไป‹็ป]

Idea 1: DFS

  • From the analysis of the problem, we only need to judge whether the child nodes of the first root node meet the requirements
  • Think of some simple, larger value does not necessarily meet the requirements, so still DFS traversal + small root heap see
  • I was actually wondering if set would work
  • If not, recursively iterate to find the node that satisfies
  • If it is not found, return -1
public int findSecondMinimumValue(TreeNode root) { //corner case PriorityQueue<Integer> priorityQueue = new PriorityQueue<Integer>(new Comparator<Integer>() @override public int compare(Integer o1, Integer o2) { if (o1 > o2) return 1; return o1.equals(o2) ? 0:1; }}); dfs(root, priorityQueue); if (priorityQueue.size() >= 2) { int min = priorityQueue.poll(); while (priorityQueue.peek()! =null){ if (priorityQueue.peek()>min){ return priorityQueue.poll(); }else{ priorityQueue.poll(); } } } return -1; } private void dfs(TreeNode root, PriorityQueue<Integer> queue) { if (root == null) { return; } queue.add(root.val); dfs(root.left, queue); dfs(root.right, queue); }Copy the code

Time complexity O(n)

The set of writing

private void dfs(TreeNode root, Set<Integer> queue) { if (root == null) { return; } queue.add(root.val); dfs(root.left, queue); dfs(root.right, queue); } public int findSecondMinimumValue(TreeNode root) { //corner case Set<Integer> set = new TreeSet<>(new @override public int compare(o1, o2) {if (o1 > o2) return 1; return o1.equals(o2) ? 0:1; }}); dfs(root, set); if (set.size() >= 2) { int i = 0; for (int num:set ) { if (i == 1){ return num; }else{ i++; } } } return -1; }Copy the code

Time complexity O(n)

DFS + pruning

  • Using the nature of binary tree pruning
  • The children of the larger element are not traversed, so we keep one as a backup
  • So DFS doesn’t have to go through both sides
public int findSecondMinimumValue(TreeNode root) { //corner case if (root.left == null){ return -1; } Set<Integer> Set = new TreeSet<>(new Comparator<Integer>() @override public int compare(o1, o1, o1) Integer o2) { if (o1 > o2) return 1; return o1.equals(o2) ? 0:1; }}); set.add(root.left.val); set.add(root.right.val); if (root.left.val == root.val) { dfs3(root.left, set); } if (root.right.val == root.val) { dfs3(root.right, set); } if (set.size() >= 2) { int i = 0; for (int num : set ) { if (i == 1) { return num; } else { i++; } } } return -1; } private void dfs3(TreeNode root, Set<Integer> set) { if (root == null) { return; } if (root.left == null) { return; } set.add(root.left.val); set.add(root.right.val); if (root.left.val == root.val) { dfs3(root.left, set); } if (root.right.val == root.val) { dfs3(root.right, set); }}Copy the code

Time complexity O(n)

Idea 3: further optimization of pruning

  • Three leaf big guy’s way

  • I actually thought about that in the previous problem

  • But still did not grasp the point and did not continue to think

  • This line of thinking depends on two conditions

    • The nodes are all positive, ensuring that the ANS updates only when it encounters a positive number
    • The minimum value of the node is passed up, which guarantees the minimum value of the root node

  • This logic ensures that the ANS will only be updated if it encounters a node larger than the minimum

  • At the same time, the ANS update does not need to go down again

  • Further optimization of pruning – all child nodes are pruned

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 code

Time complexity O(n)