LeetCode - Easy - 671. Second Minimum Node In a Binary Tree

红太狼 2022-10-06 09:57 105阅读 0赞

## Topic ##

*  Tree

## Description ##

[https://leetcode.com/problems/second-minimum-node-in-a-binary-tree/][https_leetcode.com_problems_second-minimum-node-in-a-binary-tree]

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. More formally, the property `root.val = min(root.left.val, root.right.val)` always holds.

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:**

![0bcc8d1bfd49276663468ef8e4c20907.png][]

Input: root = [2,2,5,null,null,5,7]
    Output: 5
    Explanation: The smallest value is 2, the second smallest value is 5.

**Example 2:**

![ac58c17f14a23e31dd1aa6a7c40abcc6.png][]

Input: root = [2,2,2]
    Output: -1
    Explanation: The smallest value is 2, but there isn't any second smallest value.

**Constraints:**

*  The number of nodes in the tree is in the range `[1, 25]`.
 *   1 < = N o d e . v a l < = 2 31 − 1 1 <= Node.val <= 2^\{31\} - 1 1<=Node.val<=231−1
 *  `root.val == min(root.left.val, root.right.val)` for each internal node of the tree.

## Analysis ##

根据`node.val = min(node.left.val, node.right.val)`性质，可推得根节点是整个树得最小值。

换个角度来说，叶子节点们两两比小，其中小者的值成为新节点的值，原先两节点成为新节点的左右子节点。然后新节点又与另一个新节点或叶子节点比小，形成新节点，以此类推，直到形成根节点，也就是众多叶子节点中最小值脱颖而出。

这个过程中，第二小的节点肯定与最小值至少有一次比较。

于是，通过DFS方式，找出曾与最小值比较过的节点值中，找出第二小的节点。

![一个例图][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTE4NjMwMjQ_size_16_color_FFFFFF_t_70_pic_center]  
具体来说用到后序遍历模式来解答。

## Submission ##

import com.lun.util.BinaryTree.TreeNode;
    
    public class SecondMinimumNodeInABinaryTree { 
        public int findSecondMinimumValue(TreeNode root) { 
            if(root == null || 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);
        }
    }

## Test ##

import static org.junit.Assert.*;
    import org.junit.Test;
    
    import com.lun.util.BinaryTree;
    
    public class SecondMinimumNodeInABinaryTreeTest { 
    
    	@Test
    	public void test() { 
    		SecondMinimumNodeInABinaryTree obj = new SecondMinimumNodeInABinaryTree();
    
    		assertEquals(5, obj.findSecondMinimumValue(BinaryTree.integers2BinaryTree(2,2,5,null,null,5,7)));
    		assertEquals(-1, obj.findSecondMinimumValue(BinaryTree.integers2BinaryTree(2,2,2)));
    	}
    }

[https_leetcode.com_problems_second-minimum-node-in-a-binary-tree]: https://leetcode.com/problems/second-minimum-node-in-a-binary-tree/
[0bcc8d1bfd49276663468ef8e4c20907.png]: /images/20221005/9574826f66f84e9e948b3dc6d06156a1.png
[ac58c17f14a23e31dd1aa6a7c40abcc6.png]: /images/20221005/a853ddf867cb41ab872f63310f2d244e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTE4NjMwMjQ_size_16_color_FFFFFF_t_70_pic_center]: /images/20221005/502dc7d15bed415abaf70fede333a4d1.png