leetcode-530：二叉搜索树的最小绝对差

问题

给你一棵所有节点为非负值的二叉搜索树，请你计算树中任意两节点的差的绝对值的最小值

示例：
输入：

1
\
3
/
2

输出：1

解释：
最小绝对差为 1，其中 2 和 1 的差的绝对值为 1（或者 2 和 3）

思路

题目中要求在二叉搜索树上任意两节点的差的绝对值的最小值。注意是二叉搜索树，二叉搜索树可是有序的
遇到在二叉搜索树上求什么最值啊，差值之类的，就把它想成在一个有序数组上求最值，求差值，这样就简单多了

解法一：递归

二叉搜索树中采用中序遍历，得到一个有序数组，然后遍历数组，统计出最小差值

class Solution {
    ArrayList<Integer> res = new ArrayList<Integer>();
    public void inorder(TreeNode root, ArrayList<Integer> res){
        if(root == null){
            return;
        }
        inorder(root.left, res);
        res.add(root.val);
        inorder(root.right, res);
    }
    public int getMinimumDifference(TreeNode root) {
        inorder(root, res);
        if(res.size() < 2){
            return 0;
        }
        int result = Integer.MAX_VALUE;
        for(int i = 1; i < res.size(); i++){
            result = Math.min(result, Math.abs(res.get(i) - res.get(i - 1)));
        }
        return result;
    }
}

以上代码是把二叉搜索树转化为有序数组了，其实在二叉搜素树中序遍历的过程中，我们就可以直接计算了。

需要用一个pre节点记录一下cur节点的前一个节点

class Solution{
    int result = Integer.MAX_VALUE;
    int pre = -1;
    public int getMinimumDifference(TreeNode root){
        traversal(root);
        return result;
    }
    public void traversal(TreeNode cur){
        if(cur == null){
            return;
        }
        traversal(cur.left); //左
        if(pre == -1){
            pre = cur.val;
        }else{
            result = Math.min(result, cur.val - pre); //中
            pre = cur.val;
        }
        traversal(cur.right); //右
    }
}

• 时间复杂度：，其中 n 为二叉搜索树节点的个数。每个节点在中序遍历中都会被访问一次且只会被访问一次
• 空间复杂度：，递归函数的空间复杂度取决于递归的栈深度，而栈深度在二叉搜索树为一条链的情况下会达到 级别

解法二：迭代

class Solution {
    public int getMinimumDifference(TreeNode root) {
        Deque<TreeNode> st = new LinkedList<TreeNode>();
        TreeNode cur = root;
        TreeNode pre = null;
        int result = Integer.MAX_VALUE;

        while (cur != null || !st.isEmpty()) {
            if (cur != null) { // 指针来访问节点，访问到最底层
                st.push(cur); // 将访问的节点放进栈
                cur = cur.left;                // 左
            } else {
                cur = st.pop();
                if (pre != null) {              // 中
                    result = Math.min(result, cur.val - pre.val); 
                }
                pre = cur;
                cur = cur.right;               // 右
            }
        }
        return result;
    }
}