> For the complete documentation index, see [llms.txt](https://hao-fu-1.gitbook.io/oj/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://hao-fu-1.gitbook.io/oj/binary_tree_and_divide_conquer/divide-and-concquer/second-minimum-node-in-a-binary-tree.md).

# 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;
    }
}
```