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

题目地址(530. 二叉搜索树的最小绝对差 - 力扣（LeetCode）)

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

题目描述

给你一个二叉搜索树的根节点 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

 

注意：本题与 783 https://leetcode-cn.com/problems/minimum-distance-between-bst-nodes/ 相同

思路：中序遍历

根据中序遍历结果，二叉搜索树的最小绝对差肯定是相邻的两个节点。因此，定义一个 prev 来存储当前节点的上一个节点情况，并假设初始绝对差为Integer.Max_VALUE 。

递归函数定义：

1. 返回值为void，参数为 root

public void traverse(TreeNode root)

递归终止条件为：如果树为空，直接返回

递归逻辑：

• 递归左子树
• 如果 prev 不为空，就要进行比较绝对差，然后进行更新结果
• 更新 prev 为 root
• 递归右子树

关键点

• 二叉搜索树的中序遍历是一个单调递增的数组

代码

• 语言支持：Java

Java Code:

/**
 * 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 {
    // 二叉搜索树中，左中右的遍历顺序是一个单调递增数组
    public int getMinimumDifference(TreeNode root) {
        traverse(root);
        return res;
    }

    TreeNode prev = null;
    int res = Integer.MAX_VALUE;

    public void traverse(TreeNode root) {
        if (root == null)
            return;

        // 左
        traverse(root.left);
        // 中
        if (prev != null) {
            res = Math.min(res, root.val - prev.val);
        }
        prev = root;
        traverse(root.right);
    }
}

复杂度分析

令 n 为二叉树节点个数。

• 时间复杂度：$O(n)$，每个节点最多遍历一次
• 空间复杂度：$O(n)$，空间复杂度与树的高度有关，最坏情况下为一条链条。

迭代写法

class Solution {
    TreeNode pre;
    Deque<TreeNode> queue;
    public int getMinimumDifference(TreeNode root) {
        if(root == null) return 0;
        queue = new ArrayDeque<>();
        TreeNode cur = root;
        int result = Integer.MAX_VALUE;
         while (cur != null || !queue.isEmpty()) {
            if (cur != null) {
                queue.offerFirst(cur); // 将访问的节点放进栈
                cur = cur.left; // 左
            }else {
                cur = queue.pollFirst(); 
                if (pre != null) { // 中
                    result = Math.min(result, cur.val - pre.val);
                }
                pre = cur;
                cur = cur.right; // 右
            }
        }
        return result;
    }
}