二叉搜索树的最小绝对差

530.二叉搜索树的最小绝对差

给你一个二叉搜索树的根节点 root ，返回 树中任意两不同节点值之间的最小差值 。

差值是一个正数，其数值等于两值之差的绝对值。

示例 1：

输入：root = [4,2,6,1,3]
输出：1

示例 2：

输入：root = [1,0,48,null,null,12,49]
输出：1

提示：

• 树中节点的数目范围是 [2, 104]
• 0 <= Node.val <= 105

迭代

class Solution {
    int min_dis = Integer.MAX_VALUE;//记录最小差值
    TreeNode pre = null;//记录前序节点
    public int getMinimumDifference(TreeNode root) {
        traversal(root);
        return min_dis;
    }

    public void traversal(TreeNode root){
        if(root==null) return;
        traversal(root.left);
        if(pre != null){
            min_dis = Math.min(min_dis, root.val - pre.val);
        }
        pre = root;
        traversal(root.right);
    }
}

迭代法（中序遍历）

class Solution {
    
    public int getMinimumDifference(TreeNode root) {
        int min_dis = Integer.MAX_VALUE; //记录最小差值
        TreeNode pre = null; //记录前序节点
        Stack<TreeNode> st = new Stack<>();
        while(root != null || !st.isEmpty()){
            while(root != null){
                st.push(root);
                root = root.left;
            }
            root = st.pop();
            if(pre != null){ 
                min_dis = Math.min(min_dis, root.val - pre.val);
            }
            pre = root; //pre指向当前访问节点
            root = root.right;
        }
        return min_dis;
    }
}