二叉搜索树中的最小绝对差

在处理二叉搜索树（BST）时，利用其有序性是优化算法的关键。二叉搜索树的中序遍历结果是一个单调递增的序列，因此任意两个节点差值的最小值，必然出现在中序遍历中相邻的两个节点之间。

通过维护一个指向前趋节点的指针，我们可以在遍历过程中实时计算差值并更新全局最小值。

public class Solution {
    private int smallestGap = int.MaxValue;
    private TreeNode prevNode = null;

    public int GetMinimumDifference(TreeNode root) {
        CalculateMinGap(root);
        return smallestGap;
    }

    private void CalculateMinGap(TreeNode current) {
        if (current == null) return;

        // 执行中序遍历：左-根-右
        CalculateMinGap(current.left);

        if (prevNode != null) {
            int currentGap = current.val - prevNode.val;
            if (currentGap < smallestGap) {
                smallestGap = currentGap;
            }
        }
        prevNode = current;

        CalculateMinGap(current.right);
    }
}

实现要点在于 prevNode 的初始化与更新。在递归过程中，prevNode 始终记录当前节点在有序序列中的前一个位置，从而避免了将树转换为显式数组的额外空间开销。

寻找二叉搜索树中的众数

如果将二叉搜索树视为一个有序数组，寻找众数的问题就变成了统计连续相同元素出现频率的问题。通过中序遍历，我们可以直接在处理节点时完成频率统计，无需使用哈希表记录所有节点的频率。

public class Solution {
    private int maxFreq = 0;
    private int currentFreq = 0;
    private TreeNode lastNode = null;
    private List<int> modes = new List<int>();

    public int[] FindMode(TreeNode root) {
        InOrderModeSearch(root);
        return modes.ToArray();
    }

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

        InOrderModeSearch(node.left);

        // 统计当前数值的频率
        if (lastNode != null && lastNode.val == node.val) {
            currentFreq++;
        } else {
            currentFreq = 1;
        }

        // 更新众数列表
        if (currentFreq > maxFreq) {
            maxFreq = currentFreq;
            modes.Clear();
            modes.Add(node.val);
        } else if (currentFreq == maxFreq) {
            modes.Add(node.val);
        }

        lastNode = node;

        InOrderModeSearch(node.right);
    }
}

在该逻辑中，每当发现更高的频率时，我们通过 modes.Clear() 清除旧的结果并存入新值；若频率持平，则将数值加入集合。这种方式保证了算法在 $O(1)$ 的额外空间复杂度（不计递归栈）下运行。

二叉树的最近公共祖先 (LCA)

寻找最近公共祖先是一个经典的回溯问题。对于给定的两个节点 $p$ 和 $q$，我们需要自底向上地搜索。如果一个节点的左子树包含了 $p$（或 $q$），而右子树包含了 $q$（或 $p$），那么该节点即为最近公共祖先。

public class Solution {
    public TreeNode LowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        // 终止条件：找到目标节点或触及叶子节点
        if (root == null || root == p || root == q) {
            return root;
        }

        // 递归向左右子树搜索
        TreeNode leftResult = LowestCommonAncestor(root.left, p, q);
        TreeNode rightResult = LowestCommonAncestor(root.right, p, q);

        // 如果左右子树各返回一个非空节点，说明当前节点就是分叉点
        if (leftResult != null && rightResult != null) {
            return root;
        }

        // 否则返回非空的那一侧搜索结果（即向上层传递已找到的节点）
        return leftResult ?? rightResult;
    }
}

这里的核心逻辑在于递归的返回值。如果 leftResult 和 rightResult 均不为空，说明当前节点是 $p$ 和 $q$ 的分叉点；如果仅有一侧不为空，说明 $p$ 和 $q$ 都在该侧，或者目前只找到了其中一个，需要继续向上传递该发现结果。