leetcode671SecondMinNodeInBinaryTree

Leetcode671. Second Minimum Node In a Binary Tree

//implementing in sort of bussiness logic in control component in
//flexibly used in front end or backend!!!

Analysis:

  1. using dfs or bfs, search the val in range (min1, ans), update ans = val if val in (min1, ans);
  2. using dfs with divide and conque, dfs to get left and right of the subtree, and only recursion on the condition of root.val == root.left.val or root.val == root.right.val;
  • solution one

    dfs

solution{
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
	int min1;
	long ans = Long.MAX_VALUE;
	public int findSecondMinimumValue(TreeNode root){
		if(root==null) return -1;
		dfs(root);
		return ans ==Long.MAX_VALUE?-1:(int)ans;
	}
	//once root.val > min1, we never drill deeply
	//only root.val == min1, we dfs left and right
	private void dfs(TreeNode root){
		if(root!=null){
			if(root.val>min1 && root.val < ans){
				ans = root.val;
			}else if(root.val == min1){
				dfs(root.left);
				dfs(root.right);
			}
		}
	}
}

bfs

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class solution{
	public int findSecondMinimumValue(TreeNode root){
		if(root==null) return -1;
		int rootval = root.val;
		long ans = Long.MAX_VALUE;
		Queue<Integer> queue = new LinkedList<>();
		queue.add(root);
		while(!queue.isEmpty()){
			TreeNode tmp = queue.poll();
			if(tmp.left != rootval && head.val < ans){
				ans = head.val;
			}
			if(tmp.left != null){
				queue.add(tmp.left);
				queue.add(tmp.right);
			}
		}
		return ans == Long.MAX_VALUE ? -1: ans;
	}
}
  • solution two

    divide and conquer with dfs

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    //only left.val == root.val or right.val == root.val will be dfs
    //be familiar to implement condition returnning in order.
    class solution{
    	public int findSecondMinimumValue(TreeNode root){
    		if(root==null) return -1;
    		if(root.left==null && root.right==null) return -1;
    		int left = root.left.val;
    		int right = root.right.val;
    		if(root.left.val == root.val){
    			left = findSecondMinimumValue(root.left);
    			}
    		if(root.right.val == root.val){
    			right = findSecondMinimumValue(root.right);
    		}
    		if(left!=-1 && right != -1){
    			return Math.min(left, rigth);
    		}
    		if(left != -1){
    			return left;
    		}else{
    		return right;
    		}
    	}
    }