leetcode671- Second Minimum Node In a Binary Tree- easy

Given a non-empty special binary tree consisting of nodes with the non-negative value, where each node in this tree has exactly twoor 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.

算法：

1. 最简单的做法就是树的遍历打擂台，类似的还有把树的节点值放到set里然后从set取第二大的值（我觉得不是很好，不确定set的iterator真的是有序的，可能只是还没冲突的时候有序）。但这些如果都是普通的树也都可以，怎么利用上这个树的性质呢。

2.用性质优化。其实不需要每个点都去遍历，利用好两个性质。1.根节点是最小值。2.如果一个点比最小值大，那它可能是次小值的candidate，但对比完它后不需要再遍历它子树中任何节点。 2的具体原因是它已经是它子树中的最小值了，不会有比它更适合当candidates的人了。用2这一点可以提早剪很多很多树枝。

3.甚至你可以做在这种树里找第k小的follow up。你如果设一个任意的base，你总可以根据这种剪枝的方法找到比base稍微大一点的数（如果>base，就比较一次剪枝，如果<= base，就递归结点的孩子）。那你知道循环k-1次，每次把base换成上一个第几小的数字，就得到答案了。

leetcode671- Second Minimum Node In a Binary Tree- easy

实现

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;
        }
        int[] min = new int[2];
        min[0] = root.val;
        min[1] = Integer.MAX_VALUE;
        helper(root, min);
        if (min[1] != Integer.MAX_VALUE) {
            return min[1];
        }
        return -1;
    }
    
    private void helper(TreeNode root, int[] min) {
        if (root == null) {
            return;
        }
        if (root.val != min[0]) {
            min[1] = Math.min(min[1], root.val);
        }
        helper(root.left, min);
        helper(root.right, min);
    }
}

2.性质优化

/**
 * 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;
    private int min2 = Integer.MAX_VALUE;
    
    public int findSecondMinimumValue(TreeNode root) {
        min1 = root.val;
        helper(root);
        return min2 == Integer.MAX_VALUE ? -1 : min2;
    }
    
    private void helper(TreeNode root) {
        if (root == null) {
            return;
        }
        if (root.val != min1) {
            min2 = Math.min(min2, root.val);
            return;
            //这个return很重要，避免继续深度遍历减了很多枝。
        }
        helper(root.left);
        helper(root.right);
    }
}

3.找第k小的follow up

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    private int base;
    private int bigger;
    
    // 找出第k大的数。
    public int findSecondMinimumValue(TreeNode root) {
        int k = 2;
        bigger = root.val;
        for (int i = 0; i < k - 1; i++) {
            base = bigger;
            bigger = Integer.MAX_VALUE;
            helper(root);            
        }
        return bigger == Integer.MAX_VALUE ? -1 : bigger;
    }
    
    private void helper(TreeNode root) {
        if (root == null) {
            return;
        }
        if (root.val > base) {
            bigger = Math.min(bigger, root.val);
            return;
            //这个return很重要，避免继续深度遍历减了很多枝。
        } else {
            helper(root.left);
            helper(root.right);
        }
    }
}

leetcode671- Second Minimum Node In a Binary Tree- easy

相关推荐