C++写出算法分析与设计中的最近对问题代码

在C++中，为了实现最近公共祖先（LCA，Least Common Ancestor）的问题，我们可以利用二叉查找树（如AVL树或红黑树）的概念。下面是一个基本的递归解决方案：

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Solution {
public:
    int lca(TreeNode* root, TreeNode* p, TreeNode* q) {
        if (!root || root == p || root == q) return root ? root->val : -1; // 如果根节点为空，或者p或q就是根，直接返回值
        
        // 分治策略：如果p和q都在左子树或右子树里，那么它们最近公共祖先也在相应的子树里
        if (root->val > p->val && root->val > q->val) {
            return lca(root->left, p, q);
        }
        else if (root->val < p->val && root->val < q->val) {
            return lca(root->right, p, q);
        }
        // 如果p和q分别在左右子树，根就是最近公共祖先
        else {
            return root->val;
        }
    }
};

这个代码定义了一个`Solution`类，其中`lca`函数接收一个二叉树的根节点和两个查找的目标节点`p`和`q`，通过比较目标节点值和当前节点值的关系，递归地缩小搜索范围直到找到最近公共祖先。