C#LeetCode刷题之#671-二叉树中第二小的节点（Second Minimum Node In a Binary Tree）

问题

给定一个非空特殊的二叉树，每个节点都是正数，并且每个节点的子节点数量只能为 2 或 0。如果一个节点有两个子节点的话，那么这个节点的值不大于它的子节点的值。 

给出这样的一个二叉树，你需要输出所有节点中的第二小的值。如果第二小的值不存在的话，输出 -1 。

输入: 

   2
   / \
  2   5
       / \
     5   7

输出: 5

说明: 最小的值是 2 ，第二小的值是 5 。

输入: 

     2
    / \
  2   2

输出: -1

说明: 最小的值是 2, 但是不存在第二小的值。

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.

Input: 

    2
   / \
  2   5
       / \
     5   7

Output: 5

Explanation: The smallest value is 2, the second smallest value is 5.

Input: 

    2
    / \
  2   2

Output: -1

Explanation: The smallest value is 2, but there isn’t any second smallest value.

示例

public class Program {

    public static void Main(string[] args) {
        var root = new TreeNode(1) {
            left = new TreeNode(3) {
                left = new TreeNode(5),
                right = new TreeNode(7)
            },
            right = new TreeNode(9)
        };

        var res = FindSecondMinimumValue(root);
        Console.WriteLine(res);

        Console.ReadKey();
    }

    public static int FindSecondMinimumValue(TreeNode root) {
        var first = int.MaxValue;
        var second = int.MaxValue;
        PreOrder(root, ref first, ref second);
        return second != int.MaxValue ? second : -1;
    }

    public static void PreOrder(TreeNode root, ref int first, ref int second) {
        //前序遍历
        if(root == null) return;
        if(root.val < first) {
            //如果当前值更比 first 还小
            //那么第 2 小变成当前最小
            //当前最小变成当前值
            second = first;
            first = root.val;
        } else if(root.val > first && root.val < second)
            //如果界面 2 者之间
            //将第 2 小变成当前值即可
            second = root.val;
        PreOrder(root.left, ref first, ref second);
        PreOrder(root.right, ref first, ref second);
    }

    public class TreeNode {
        public int val;
        public TreeNode left;
        public TreeNode right;
        public TreeNode(int x) { val = x; }
    }

}

以上给出1种算法实现，以下是这个案例的输出结果：

3

分析：

显而易见，以上算法的时间复杂度为： ​ 。