[数据结构与算法]算法题目：二叉树中第二小的节点

思路：使用深度优先遍历，比较每个节点的大小，最后得出结论。但是该题目可以减枝，由于题目的特性root.val = min(root.left.val, root.right.val)，所以得出根节点是最小的节点，并且父节点第二小的节点的父节点一定等于根节点的值。通过以上两种特性来进行遍历和减枝操作。

?观察树结合该题目的条件，我们不难发现，图中的③④节点无论如何往下衍生，都只会是这两个节点最小，所以每次只需要比较父节点的值等于根节点的值的节点的值是否是第二小。

?代码如下：

public class question_671 {
    /**
     * Definition for a binary tree node.
     */
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode() {}
        TreeNode(int val) { this.val = val; }
        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
    class Solution {
        // 第二小的值
        int res = -1;
        // 根节点的值
        int r = 0;
        public int findSecondMinimumValue(TreeNode root) {
            if(root==null) {
                return res;
            }
            r = root.val;
            dfs(root);
            return res;
        }
        public void dfs(TreeNode node) {
            // 直接判断一个节点为null  题目说明了只可能同时存在两个子节点
            if(node.left==null) {
                //说明已经到了最底层
                return;
            }
            getRes(node.left);
            getRes(node.right);
        }
        public void getRes(TreeNode node) {
            // 如果节点等于根节点 则继续遍历
            if(r == node.val) {
                dfs(node);
            } else {
                // 减枝操作，如果不等于根节点则直接判断大小即可，
                // 因为接下来的节点一定比他大 没有比较的必要
                if(res == -1) {
                    res = node.val;
                } else {
                    res = Math.min(res, node.val);
                }
            }
        }
    }
}