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);}