原文标题写着「中序遍历」，但实际函数名是 getMinimumDifference，对应的是 LeetCode 530「二叉搜索树的最小绝对差」。这里把题意和迭代式中序遍历的原理简单说明一下，代码保留原样。

题目背景

LeetCode 530：给定一棵 BST，求任意两节点值的差的绝对值的最小值。

概念解释

中序遍历（inorder）：左子树 → 根 → 右子树。BST 的中序遍历结果是严格递增的有序序列。
栈式迭代中序遍历：利用一个显式栈模拟系统栈，避免递归。每次先把所有左孩子压栈，弹栈即得到当前最小未访问节点，再以它的右子树作为新的子问题继续。

实现原理

由于 BST 中序遍历结果有序，最小绝对差只可能出现在有序序列相邻两项之间（任何非相邻对之间的差都大于某对相邻差）。

代码做了两步：

用栈做迭代式中序遍历，把节点值依次写入 arr，得到一个递增数组。
扫描相邻元素差 |arr[i] - arr[i-1]|，取最小值返回。

时间复杂度 O(n)：每个节点入栈出栈各一次；空间复杂度 O(h)，h 为树高（栈最大深度），结果数组额外占 O(n)。

备注：原代码用 0x33333333L 作为 INT_MAX 初始值，含义是”足够大的初值”，实践中可以替换成 INT_MAX 让意图更直观。这里保留原写法。

参考实现

中序遍历

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
private:
    std::vector<int> arr;
public:
    int getMinimumDifference(TreeNode* root) {
        std::stack<TreeNode*> s;
        bool flag = false;

        if(root == nullptr)
        {
            return -1;
        }
        
        while(true)
        {
            while(root != nullptr)
            {
                s.emplace(root);
                root = root->left;
            }

            if(!s.empty())
            {
                TreeNode* t = s.top();
                s.pop();
                arr.emplace_back(t->val);
                // std::cout << t->val << std::endl;

                if(t->right != nullptr)
                {
                    root = t->right;
                }
            }else
            {
                break;
            }
        }

        int min = 0x33333333L;

        for(auto i = 1; i < arr.size(); ++i)
        {
            int t = std::abs(arr[i] - arr[i - 1]);
            // std::cout << arr[i] << " " << arr[i - 1] << std::endl;
            if(min > t)
            {
                min = t;
            }
        }

        return  min;

    }
};

FEATURED TAGS

Git Cheat Sheet Markdown Tools C++ Linker Thread Linux TCP Network GDB Debug leetcode 链表 WSL Ubuntu Windows Linux Kernel GCC Android adb Troubleshooting Profiling Sanitizer glibc MySQL Database Python curl Build ELF clang-format CMake Graphviz Performance vcpkg Protobuf 排查速查内存 STL 调试性能分析性能读书笔记方法论架构网络 Timer mbedTLS TLS 安全负载均衡脚本工具 LRU 二叉树 BST 中序遍历回溯二分查找优先队列排序旋转数组 jenkins 部署

二叉搜索树中序遍历（求最小绝对差）

LeetCode 530 题解笔记

CATALOG