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

深度优先搜索

class Solution {

    int res = Integer.MAX_VALUE;
    TreeNode prev;

    public int getMinimumDifference(TreeNode root) {

        if (root == null){
            return 0;
        }

        /**
         * 中序遍历
         * 在遍历每一个节点的时候，保存上一个遍历的节点，然后计算差值
         * 由于是中序遍历，遍历的顺序是从小到大，因此root.val - prev.val始终大于0
         */
        getMinimumDifference(root.left);

        if (prev != null){
            res = Math.min(res, root.val - prev.val);
        }

        prev = root;

        getMinimumDifference(root.right);

        return res;
    }
}

/**
 * 时间复杂度 O(n)
 * 空间复杂度 O(n)
 */

迭代

class Solution {

    int res = Integer.MAX_VALUE;
    TreeNode prev;

    public int getMinimumDifference(TreeNode root) {

        if (root == null){
            return 0;
        }

        Stack stack = new Stack<>();
        TreeNode cur = root;

        /**
         * 中序遍历
         */
        while (cur != null || !stack.isEmpty()){

            if (cur != null){

                stack.push(cur);
                cur = cur.left;
            }
            else {

                cur = stack.pop();

                if (prev != null){
                    res = Math.min(res, cur.val - prev.val);
                }

                prev = cur;
                cur = cur.right;
            }
        }

        return res;
    }
}

/**
 * 时间复杂度 O(n)
 * 空间复杂度 O(n)
 */

https://leetcode-cn.com/problems/minimum-absolute-difference-in-bst/