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

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

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) —

推荐阅读：
期中考试350字　 早起的感觉真好作文600字　 沉默日志：为了忘却的纪念　 直面挫折战胜困难　 我们不说再见　 写人作文你看他们俩作文　 “三八”妇女节作文　 放青蛙作文150字　 爱之伟大——读《地震中的父与子》有感700字　 游泗北新城记作文500字　
评论列表
添加评论