二叉搜索树的最小绝对差

题目描述

力扣链接🔗

代码分析

数组法

还是可以利用二叉搜索树的特性，中序遍历之后的数组一定是递增的。但数组法的时间复杂度为O(n ^ n)。

/**
 * 遍历搜索树为一个数组，进行判断即可（时间复杂度要高一点）
 *
 * @param root
 * @return
 */
public int getMinimumDifference(TreeNode root) {
    traversal(root);
    for (int i = 1; i < res.size(); i++) {
        minValue = Math.min(minValue, Math.abs(res.get(i) - res.get(i - 1)));
    }
    return minValue;
}
List<Integer> res = new ArrayList<>();
int minValue = Integer.MAX_VALUE;
public TreeNode traversal(TreeNode root) {
    if (root == null) {
        return null;
    }
    traversal(root.left); // 左
    res.add(root.val);
    traversal(root.right); // 右
    return root;
}

递归法

思路和验证二叉搜索树大体一致，需要找到最左边的节点来进行相减判断。

/**
 * 递归法
 *
 * @param root
 * @return
 */
public int getMinimumDifference(TreeNode root) {
    if (root == null) {
        return 0;
    }
    traversal(root);
    return minValue;
}
int minValue = Integer.MAX_VALUE;
TreeNode pre;   // 表示前一个节点，一定要定义为全局变量，在递归函数中定义，每次会重新赋值为null，就找不到上一个节点的值
public TreeNode traversal(TreeNode root) {
    if (root == null) {
        return null;
    }
    traversal(root.left); // 左
    if (pre != null) minValue = Math.min(minValue, Math.abs(root.val - pre.val));   // 中
    pre = root;
    traversal(root.right); // 右
    return root;
}

迭代法

和二叉搜索树的验证一致，也是获取上一个节点，但是判断条件有所改变。

/**
 * 迭代法(中序)
 *
 * @param root
 * @return
 */
public int getMinimumDifference(TreeNode root) {
    Stack<TreeNode> stack = new Stack<>();
    TreeNode cur = root;
    TreeNode pre = null;
    int minValue = Integer.MAX_VALUE;
    while (cur != null || !stack.isEmpty()) {
        if (cur != null) {
            stack.push(cur);
            cur = cur.left;
        } else {
            cur = stack.pop();
            if (pre != null) {
                minValue = Math.min(minValue, Math.abs(cur.val - pre.val));
            }
            pre = cur;
            cur = cur.right;    // 获取右孩子
        }
    }
    return minValue;
}