LeetCode 783. 二叉搜索树节点最小距离

Categories:

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

题目描述

✅ 783. 二叉搜索树节点最小距离

思路分析

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

核心思路：

BST 中序遍历得到递增序列。

只需比较相邻元素差值的最小值。

用 prev 记录前一个节点值。

复杂度分析：

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

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

class Solution {
    private Integer prev = null;
    private int ans = Integer.MAX_VALUE;

    public int minDiffInBST(TreeNode root) {
        inorder(root);
        return ans;
    }

    private void inorder(TreeNode node) {
        if (node == null) {
            return;
        }

        inorder(node.left);

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

        inorder(node.right);
    }
}

func minDiffInBST(root *TreeNode) int {
	prevSet := false
	prev := 0
	ans := int(^uint(0) >> 1)

	var inorder func(node *TreeNode)
	inorder = func(node *TreeNode) {
		if node == nil {
			return
		}

		inorder(node.Left)

		if prevSet {
			diff := node.Val - prev
			if diff < ans {
				ans = diff
			}
		}
		prev = node.Val
		prevSet = true

		inorder(node.Right)
	}

	inorder(root)
	return ans
}

相似题目

题目	难度	考察点
530. 二叉搜索树的最小绝对差	简单	BST 中序
98. 验证二叉搜索树	中等	BST
230. 二叉搜索树中第K小的元素	中等	BST
501. 二叉搜索树中的众数	简单	BST
700. 二叉搜索树中的搜索	简单	BST

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2023/48755883