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

Categories:

题目描述
思路分析
1. 解法一：中序遍历（推荐）
相似题目

题目描述

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

思路分析

解法一：中序遍历（推荐）

核心思路：

BST 的中序遍历序列递增。

只需比较相邻节点的差值即可得到最小绝对差。

用 prev 记录上一个访问节点。

复杂度分析：

时间复杂度：O(n)，其中 n 表示节点数量。

空间复杂度：O(h)，其中 h 表示树高（栈深）。

class Solution {
    public int getMinimumDifference(TreeNode root) {
        Deque<TreeNode> stack = new ArrayDeque<>();
        TreeNode cur = root;
        Integer prev = null;
        int ans = Integer.MAX_VALUE;

        // 中序遍历保持递增
        while (cur != null || !stack.isEmpty()) {
            while (cur != null) {
                stack.push(cur);
                cur = cur.left;
            }

            cur = stack.pop();
            if (prev != null) {
                ans = Math.min(ans, cur.val - prev);
            }
            prev = cur.val;
            cur = cur.right;
        }

        return ans;
    }
}

func getMinimumDifference(root *TreeNode) int {
	stack := make([]*TreeNode, 0)
	cur := root
	prev := -1
	ans := int(^uint(0) >> 1)

	// 中序遍历保持递增
	for cur != nil || len(stack) > 0 {
		for cur != nil {
			stack = append(stack, cur)
			cur = cur.Left
		}

		cur = stack[len(stack)-1]
		stack = stack[:len(stack)-1]

		if prev != -1 {
			if cur.Val-prev < ans {
				ans = cur.Val - prev
			}
		}
		prev = cur.Val
		cur = cur.Right
	}

	return ans
}

相似题目

题目	难度	考察点
783. 二叉搜索树节点最小距离	简单	中序遍历
98. 验证二叉搜索树	中等	BST
230. 二叉搜索树中第 K 小的元素	中等	BST
530. 二叉搜索树的最小绝对差	简单	BST
700. 二叉搜索树中的搜索	简单	BST

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2022/70595944