How to Find Second Minimum Node In a Binary Tree (Java)?

  • 时间：2020-10-12 15:56:23
  • 分类：网络文摘
  • 阅读：221 次

Given a non-empty special binary tree consisting of nodes with the non-negative value, where each node in this tree has exactly two or zero sub-node. If the node has two sub-nodes, then this node’s value is the smaller value among its two sub-nodes.

Given such a binary tree, you need to output the second minimum value in the set made of all the nodes’ value in the whole tree.

If no such second minimum value exists, output -1 instead.

Example 1:
Input: 

    2
   / \
  2   5
     / \
    5   7

Output: 5
Explanation: The smallest value is 2, the second smallest value is 5.
Example 2:
Input:

2
/ \
2 2

Output: -1
Explanation: The smallest value is 2, but there isn’t any second smallest value.

The target is to find the second minimum in a special binary tree where the root nodes are the smallest (minimal heap). There are a few algorithms that could solve this problem.

Bruteforce with Breadth First Search

If we don’t make use of the mini-heap properties of the binary tree, we can simply bruteforce the binary tree, putting all nodes in an array, sort them, then we can easily obtain the second minimal value. However, we need to make sure duplicate nodes are only inserted in the array once.

The following BFS uses a queue to do the iterative search level by level.

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

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public int findSecondMinimumValue(TreeNode root) {
        if (root == null) {
            return -1;
        }
        Queue<TreeNode> q = new LinkedList<>();
        Set<Integer> s = new HashSet<>();
        List<Integer> a = new ArrayList<>();
        q.add(root);
        while (!q.isEmpty()) {
            TreeNode p = q.poll();
            if (!s.contains(p.val)) {
                a.add(p.val);
            }
            s.add(p.val);
            if (p.left != null) { q.add(p.left); }
            if (p.right != null) { q.add(p.right); }
        }
        Collections.sort(a);
        return a.size() >= 2 ? a.get(1) : -1;
    }
}
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public int findSecondMinimumValue(TreeNode root) {
        if (root == null) {
            return -1;
        }
        Queue<TreeNode> q = new LinkedList<>();
        Set<Integer> s = new HashSet<>();
        List<Integer> a = new ArrayList<>();
        q.add(root);
        while (!q.isEmpty()) {
            TreeNode p = q.poll();
            if (!s.contains(p.val)) {
                a.add(p.val);
            }
            s.add(p.val);
            if (p.left != null) { q.add(p.left); }
            if (p.right != null) { q.add(p.right); }
        }
        Collections.sort(a);
        return a.size() >= 2 ? a.get(1) : -1;
    }
}

The time complexity is O(nlogn) where the most time consuming part is sorting.

Bruteforce with Depth First Search in Recursion

The same idea as above could be implemented in DFS (Depth First Search) in the form of recursion where the compiler generates and maintains the stack automatically for you.

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

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    private void dfs(TreeNode root, Set<integer> s) {
        if (root == null) {
            return;
        }
        if (!s.contains(root.val)) {
            s.add(root.val);
        }
        dfs(root.left, s);
        dfs(root.right, s);
    }
        
    public int findSecondMinimumValue(TreeNode root) {
        if (root == null) {
            return -1;
        }
        Set<Integer&t; a = new HashSet<>();
        dfs(root, a);
        List<Integer> b = new ArrayList<>(a);
        Collections.sort(b);
        return b.size() >= 2 ? b.get(1) : -1;
    }
}
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    private void dfs(TreeNode root, Set<integer> s) {
        if (root == null) {
            return;
        }
        if (!s.contains(root.val)) {
            s.add(root.val);
        }
        dfs(root.left, s);
        dfs(root.right, s);
    }
        
    public int findSecondMinimumValue(TreeNode root) {
        if (root == null) {
            return -1;
        }
        Set<Integer&t; a = new HashSet<>();
        dfs(root, a);
        List<Integer> b = new ArrayList<>(a);
        Collections.sort(b);
        return b.size() >= 2 ? b.get(1) : -1;
    }
}

O(nlogn) time complexity.

Optimised DFS

The above two solutoins both use the set to avoid duplicate numbers. Let’s make min1 = root.val, as we are only interested in the second minimal number, if at any node we have the value larger than min1, we don’t need to search that sub-tree.

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

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    private int min1;
    long ans = Long.MAX_VALUE;
    
    private void dfs(TreeNode root) {
        if (root == null) return;
        if (min1 < root.val && root.val < ans) {
            ans = root.val;
        } else if (min1 == root.val) {
            dfs(root.left);
            dfs(root.right);
        }
    }
    
    public int findSecondMinimumValue(TreeNode root) {
        min1 = root.val;
        dfs(root);
        return ans < Long.MAX_VALUE ? (int)ans : -1;
    }
}
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    private int min1;
    long ans = Long.MAX_VALUE;
    
    private void dfs(TreeNode root) {
        if (root == null) return;
        if (min1 < root.val && root.val < ans) {
            ans = root.val;
        } else if (min1 == root.val) {
            dfs(root.left);
            dfs(root.right);
        }
    }
    
    public int findSecondMinimumValue(TreeNode root) {
        min1 = root.val;
        dfs(root);
        return ans < Long.MAX_VALUE ? (int)ans : -1;
    }
}

This approach is superior in terms of space complexity.

Depth First Search on Two Sub Trees

The second minimum would be the minimal of the first values of both sub tree that are bigger than the root value. If no such values are existent, we return -1.

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

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {    
    private int dfs(TreeNode root, int m) {
        if (root == null) {
            return Integer.MAX_VALUE;
        }
        if (root.val > m) {
            return root.val;
        }        
        int min1 = dfs(root.left, m);
        int min2 = dfs(root.right, m);
        return Math.min(min1, min2);
    }
    
    public int findSecondMinimumValue(TreeNode root) {
        int v = dfs(root, root.val);
        return v == Integer.MAX_VALUE ? -1 : v;
    }
}
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {    
    private int dfs(TreeNode root, int m) {
        if (root == null) {
            return Integer.MAX_VALUE;
        }
        if (root.val > m) {
            return root.val;
        }        
        int min1 = dfs(root.left, m);
        int min2 = dfs(root.right, m);
        return Math.min(min1, min2);
    }
    
    public int findSecondMinimumValue(TreeNode root) {
        int v = dfs(root, root.val);
        return v == Integer.MAX_VALUE ? -1 : v;
    }
}

Similarly, we can compare the root value to each subtree, and return the minimal of both sub-min values.

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

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {    
    public int findSecondMinimumValue(TreeNode root) {
        if(root.left == null)   return -1;
        
        int left  = (root.left.val  == root.val) ? findSecondMinimumValue(root.left)  : root.left.val;
        int right = (root.right.val == root.val) ? findSecondMinimumValue(root.right) : root.right.val;
 
        if(left  == -1)         return right;
        if(right == -1)         return left;
 
        return Math.min(left, right);
    }
}
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {    
    public int findSecondMinimumValue(TreeNode root) {
        if(root.left == null)   return -1;
        
        int left  = (root.left.val  == root.val) ? findSecondMinimumValue(root.left)  : root.left.val;
        int right = (root.right.val == root.val) ? findSecondMinimumValue(root.right) : root.right.val;

        if(left  == -1)         return right;
        if(right == -1)         return left;

        return Math.min(left, right);
    }
}

–EOF (The Ultimate Computing & Technology Blog) —

推荐阅读：
食品安全事件：商家无良心消费不放心　 食药总局启动《食品安全法》修订工作　 炎炎夏日怎样选择冰棍雪糕更安全？　 问题“毒皮蛋”再引食品安全大讨论　 教你六招辨别保健食品真假的方法　 警惕保健食品的五大非法宣传“陷阱”　 官员竟然称质疑转基因食品是民众无知　 转基因食品的利与弊及潜在危害浅析　 食品安全法即将修订 有奖举报或将入法　 辽宁省曝光十大食品犯罪典型案例　
评论列表
添加评论