671. 二叉树中第二小的节点

给定一个非空特殊的二叉树，每个节点都是正数，并且每个节点的子节点数量只能为 2 或 0。
如果一个节点有两个子节点的话，那么该节点的值等于两个子节点中较小的一个。
更正式地说，即 root.val = min(root.left.val, root.right.val) 总成立。
给出这样的一个二叉树，你需要输出所有节点中的 第二小的值 。
如果第二小的值不存在的话，输出 -1 。

示例 1：
输入：root = [2,2,5,null,null,5,7]

      2      
    /   \    
  2       5  
         / \ 
        5   7

输出：5
解释：最小的值是 2 ，第二小的值是 5 。

示例 2：
输入：root = [2,2,2]

   2   
  / \  
 2   2

输出：-1
解释：最小的值是 2, 但是不存在第二小的值。
�
如果需要找到二叉树中节点的最大值该如何查找（1 <= Node.val <= 2³¹ - 1）？

int maxVal = -1;
public int findMaxValue(TreeNode root) {
    order(root);
    return maxVal;
}
private void order(TreeNode node) {
    if (node == null) {
        return;
    }
    if (node.val > maxVal) {
        maxVal = node.val;
    }
    order(node.left);
    order(node.right);
}

如果需要找到二叉树中节点的第二大值该如何查找（1 <= Node.val <= 2³¹ - 1）？

int maxVal = -1;
int secondMaxVal = -1;
public int findSecondMaxValue(TreeNode root) {
    order(root);
    return secondMaxVal;
}
private void order(TreeNode node) {
    if (node == null) {
        return;
    }
    if (node.val > maxVal) {
        // 若当前值比已知最大值大，则将原最大值赋值给第二大值，将当前值作为新的最大值
        secondMaxVal = maxVal;
        maxVal = node.val;
    } else {
        // 若当前值没有比已知最大值大
        if (node.val != maxVal && node.val > secondMaxVal) {
            // 若当前值和已知最大值不相等，且比第二大值大，则将当前值作为新的第二大值
            secondMaxVal = node.val;
        }
    }
    order(node.left);
    order(node.right);
}

同理如何找到二叉树的最小值呢（1 <= Node.val <= 2³¹ - 1）？

int minVal = Integer.MAX_VALUE;
public int findMinValue(TreeNode root) {
    order(root);
    return minVal;
}
private void order(TreeNode node) {
    if (node == null) {
        return;
    }
    if (node.val < minVal) {
        minVal = node.val;
    }
    order(node.left);
    order(node.right);
}

那么同理可以找到二叉树的第二小值（1 <= Node.val <= 2³¹ - 1）？

int minVal = Integer.MAX_VALUE;
int secondMinVal = Integer.MAX_VALUE;
public int findSecondMinimumValue(TreeNode root) {
    order(root);
    if (!isSecondMinValChange) {
        return -1;
    }
    return secondMinVal;
}
private void order(TreeNode node) {
    if (node == null) {
        return;
    }
    if (node.val < minVal) {
        secondMinVal = minVal;
        minVal = node.val;
    } else {
        if (node.val != minVal && node.val < secondMinVal) {
            secondMinVal = node.val;
        }
    }
    order(node.left);
    order(node.right);
}

测试时有个测试用例无法通过，root = [2,2,2]，因为所有的节点值都相同，所以 secondMinVal 还是 Interger.MAX_VALUE
所以需要标记一下 secondMinVal 是否发生过修改

int minVal = Integer.MAX_VALUE;
int secondMinVal = Integer.MAX_VALUE;
boolean isSecondMinValChange = false;
public int findSecondMinimumValue(TreeNode root) {
    order(root);
    if (!isSecondMinValChange) {
        return -1;
    }
    return secondMinVal;
}
private void order(TreeNode node) {
    if (node == null) {
        return;
    }
    if (node.val < minVal) {
        secondMinVal = minVal;
        minVal = node.val;
    } else {
        if (node.val != minVal && node.val < secondMinVal) {
            secondMinVal = node.val;
            isSecondMinValChange = true;
        }
    }
    order(node.left);
    order(node.right);
}

测试时有个测试用例无法通过，root = [2,2,2147483647]，因为右节点值和 secondMinVal 相同，导致以为 secondMinVal 没有发生修改，
所以需要修改一下判断 node.val != minVal && node.val < secondMinVal 改为 node.val != minVal && node.val <= secondMinVal

int minVal = Integer.MAX_VALUE;
int secondMinVal = Integer.MAX_VALUE;
boolean isSecondMinValChange = false;
public int findSecondMinimumValue(TreeNode root) {
    order(root);
    if (!isSecondMinValChange) {
        return -1;
    }
    return secondMinVal;
}
private void order(TreeNode node) {
    if (node == null) {
        return;
    }
    if (node.val < minVal) {
        secondMinVal = minVal;
        minVal = node.val;
    } else {
        if (node.val != minVal && node.val <= secondMinVal) {
            secondMinVal = node.val;
            isSecondMinValChange = true;
        }
    }
    order(node.left);
    order(node.right);
}

但是本题有特殊性，本题其实已经限定根节点已经是最小值了，故只需要和根节点比较即可

int minVal = -1;
int rootValue;
public int findSecondMinimumValue(TreeNode root) {
    rootValue = root.val;
    order(root);
    return minVal;
}
private void order(TreeNode node) {
    if (node == null) {
        return;
    }
    if (node.val > rootValue) {
        minVal = node.val;
    }
    order(node.left);
    order(node.right);
}

但是如果一直比较，minVal 可能会一直发生变化，而实际上只要保证 minVal 只修改一次，那么最终 minVal 就是第二小的值

int minVal = -1;
int rootValue;
public int findSecondMinimumValue(TreeNode root) {
    rootValue = root.val;
    order(root);
    return minVal;
}
private void order(TreeNode node) {
    if (node == null) {
        return;
    }
    if (minVal != -1 && node.val >= minVal) {
        return;
    }
    if (node.val > rootValue) {
        minVal = node.val;
    }
    order(node.left);
    order(node.right);
}