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

本题目标是找出二叉搜索树中任意两个节点之间的最小绝对差值。由于二叉搜索树的中序遍历结果是严格递增序列，因此最小差值一定出现在某两个相邻节点之间。

直接中序遍历并记录前一个访问的节点，利用指针 prev 跟踪前驱节点，在遍历过程中实时计算当前节点与前驱节点的差值，并更新全局最小值。这种方法避免了额外数组存储，空间复杂度为 O(h)，其中 h 是树的高度（递归栈深度）。

class Solution {
private:
    TreeNode* prev = nullptr;
    int minDiff = INT_MAX;

    void inorder(TreeNode* node) {
        if (!node) return;
        inorder(node->left);
        
        if (prev != nullptr) {
            minDiff = min(minDiff, node->val - prev->val);
        }
        prev = node;

        inorder(node->right);
    }

public:
    int getMinimumDifference(TreeNode* root) {
        inorder(root);
        return minDiff;
    }
};

该实现方式简洁且充分利用了 BST 的性质，时间复杂度为 O(n)，每个节点仅被访问一次。

501. 二叉搜索树中的众数

要求找出二叉搜索树中出现次数最多的数值。若使用哈希表统计所有节点频次，虽能解决问题但未体现 BST 特性。更优策略是结合中序遍历与双指针技术，实现一次遍历完成众数查找。

核心思路：在中序遍历中相同值的节点会连续出现。通过维护前驱节点指针 prev 和当前值计数器 count，可动态判断频率变化。同时维护最大频率 maxCount，并在遍历中决定是否将当前值加入结果集。

当当前节点与前驱值相等时，count++；否则重置计数。若当前计数等于最大频率，则加入结果；若超过，则清空原结果并重新添加。这样可在不使用额外容器的情况下完成处理。

class Solution {
private:
    TreeNode* prev = nullptr;
    int count = 0;
    int maxCount = 0;
    vector<int> result;

    void inorder(TreeNode* node) {
        if (!node) return;
        inorder(node->left);

        if (prev && prev->val == node->val) {
            count++;
        } else {
            count = 1;
        }

        if (count > maxCount) {
            maxCount = count;
            result.clear();
            result.push_back(node->val);
        } else if (count == maxCount) {
            result.push_back(node->val);
        }

        prev = node;
        inorder(node->right);
    }

public:
    vector<int> findMode(TreeNode* root) {
        inorder(root);
        return result;
    }
};

此方法时间复杂度为 O(n)，空间复杂度为 O(h + k)，其中 k 为众数个数，完全基于 BST 性质优化。

236. 二叉树的最近公共祖先

给定无父指针的二叉树和两个指定节点 p、q，寻找其最低公共祖先（LCA）。不能依赖中序索引定位，而应采用后序遍历进行自底向上搜索。

递归逻辑如下：从根节点开始，分别在左右子树查找 p 和 q。如果某一子树返回空，说明两个节点均不在该侧；若左右子树各返回一个非空节点，则当前根即为 LCA；若只有一侧非空，则 LCA 在该侧。

递归函数设计关键在于返回值语义：返回以当前节点为根的子树中是否包含 p 或 q。若当前节点是 p 或 q，也立即返回该节点。

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if (!root || root == p || root == q) return root;

        TreeNode* left = lowestCommonAncestor(root->left, p, q);
        TreeNode* right = lowestCommonAncestor(root->right, p, q);

        if (left && right) return root;
        return left ? left : right;
    }
};

该解法时间复杂度为 O(n)，每个节点访问一次；空间复杂度为 O(h)，由递归栈深度决定。无需任何辅助数据结构，逻辑清晰且高效。