0530. Minimum Absolute Difference in BST

题目信息

题号:

0530

难度:

Easy

主题:

二叉搜索树、不同节点、绝对差、最小值

原题:

LeetCode 0530

重点:

比较树中任意两个不同节点值、BST 节点值互不相同、返回最小绝对差

题目重述

给定一棵至少包含两个节点的二叉搜索树,计算树中任意两个不同节点的值之差的绝对值,并返回其中的最小值。

树中所有节点值互不相同,且均为非负整数。只返回最小差值,不需要返回对应节点;节点在树中的父子距离不影响比较,任意两个节点都可以组成一对。

自建示例

最小差值来自不同分支:

输入:root = [8,3,10,1,6,null,14]
输出:2
解释:节点值按升序为 1、3、6、8、10、14,最小相邻差值为 2。

最小差值为一:

输入:root = [2,1,5]
输出:1
解释:节点 1 与节点 2 的绝对差为 1,是所有节点对中的最小值。

BST 中序序列的相邻差值

二叉搜索树中序遍历得到严格递增的节点值序列。对有序序列,任意非相邻两值的差不会小于它们之间某个相邻差,因此只需要比较连续访问节点的差值即可得到全局最小绝对差。

C++ 实现

class Solution {
    TreeNode* previous = nullptr;
    int answer = INT_MAX;

    void inorder(TreeNode* node) {
        if (node == nullptr) return;
        inorder(node->left);
        if (previous != nullptr) {
            answer = std::min(answer, node->val - previous->val);
        }
        previous = node;
        inorder(node->right);
    }

public:
    int getMinimumDifference(TreeNode* root) {
        previous = nullptr;
        answer = INT_MAX;
        inorder(root);
        return answer;
    }
};

代码分析

中序顺序把任意节点对问题化为相邻差值问题,节点值互不相同使差值为正;递归访问每个节点一次。时间复杂度为 O(n),递归栈空间为 O(h)。