Second Minimum Node In a Binary Tree

https://leetcode.com/problems/second-minimum-node-in-a-binary-tree/description/

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.

Thoughts

看到二叉树先想分治。 如果只返回当前结点对应的子树的倒数第二小的值是否就够了？ 不够，比如左边是min和sec是0,2,而右边是1,2，则算得结果会是2，而实际上是1. 那我们可以进一步多返回个sec，然后四个数比大小。为什么四个数一定够了呢？ 因为倒数第二小无非是四种情况：倒数第一小在左倒数第二小在右，反过来，倒数第一和第二都在左或右。

Code

class Solution {
    int lastMin, secondMin;
    private int[] lastAndSecMin(TreeNode root) {
        int[] result = new int[2];
        if (root == null) {
            result[0] = 0;
            result[1] = 0;
            return result;
        }

        int[] left = lastAndSecMin(root.left);
        int[] right = lastAndSecMin(root.right);
        int[] res = new int[5];
        for (int i = 0; i < 2; i++) {
            res[i] = left[i];
        }
        for (int i = 0; i < 2; i++) {
            res[i + 2] = right[i];
        }
        res[4] = root.val;
        Arrays.sort(res);
        int min = 0;  
        for (int i = 0; i < 5; i++) {
            if (res[i] != min) {
                min = res[i];
                break;
            }
        }
        int secMin = min;
        for (int i = 0; i < 5; i++) {
            if (res[i] != secMin && res[i] != 0) {
                secMin = res[i];
                break;
            }
        }

        result[0] = min;
        result[1] = secMin;
        return result;
    }

    public int findSecondMinimumValue(TreeNode root) {
        int[] mins = lastAndSecMin(root);
        if (mins[0] == mins[1]) {
            return -1;
        } else {
            return mins[1];
        }
    }
}

Analysis

时间复杂度O(n)

Ver.2

上面的解法是针对任何二叉树找sec min. 这道题的树有它的特殊性, 比如它只有0或两个节点, 而且一定是它所在子树中最小的. 也就是说root一定是最小的, 且每棵子树的root的都是最小的, 那我们只要往下找到一个和root不同且比另一边返回值小的返回即可.

class Solution {
    private int min(TreeNode root, int first) {
        if (root == null) {
            return -1;
        }
        if (root.val != first) {
            return root.val;
        }
        int left = min(root.left, root.val);
        int right = min(root.right, root.val);
        if (left == -1) {
            return right;
        } else if (right == -1) {
            return left;
        }
        return Math.min(left, right);
    }

    public int findSecondMinimumValue(TreeNode root) {
        return min(root, root.val);
    }
}

Ver.3

iterative traversal. 不过没太用上给的特殊树的性质.

/**
 * 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;
        }
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        int min = root.val, secMin = Integer.MAX_VALUE;
        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            if (node.val != min) {
                secMin = Math.min(secMin, node.val);
            }
            if (node.right != null) {
                stack.push(node.right);
            }
            if (node.left != null) {
                stack.push(node.left);
            }
        }

        return secMin == Integer.MAX_VALUE ? -1 : secMin;
    }
}