给定一棵树和两个不同的结点，求出他们最近的公共祖先父结点。 已知该树有 n 个结点，标号 1..n 。c++

给定一棵有 n 个节点的树以及两个特定节点 u 和 v 的搜索问题，要求找到它们最近的公共祖先（LCA，Least Common Ancestor），你可以使用递归算法或者层次遍历的方式解决。在 C++ 中，这里是一种常见的方法：

首先，假设每个节点都有一个指向上一级父节点的引用 `parent`，并且有一个数组 `height` 来存储每个节点的高度（距离根节点的距离）。我们可以从根节点开始，如果 u 或 v 都大于当前节点，说明这个节点不是他们的祖先，然后分别检查 u 和 v 的高度是否大于当前高度加一（因为它们可能是下一级的祖先），如果是，则继续查找下一级，直到找到一个高度相等的节点或者达到叶子节点。

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode* parent; // 父节点指针
    int height; // 节点高度
};

TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* u, TreeNode* v) {
    if (!root || root == u || root == v) return root;

    // 如果 u 或 v 的高度都比当前节点高，向上传递
    int uHeight = height[u], vHeight = height[v];
    if (uHeight > height[root]) {
        root = lowestCommonAncestor(root->parent, u, root);
    } else if (vHeight > height[root]) {
        root = lowestCommonAncestor(root->parent, v, root);
    }

    // 如果 u 和 v 高度相同，则返回当前节点
    return uHeight == vHeight ? root : nullptr;
}

void initializeHeight(TreeNode* node, int depth) {
    node->height = depth;
    if (node->left) initializeHeight(node->left, depth + 1);
    if (node->right) initializeHeight(node->right, depth + 1);
}

要实现此功能，你需要先计算整棵树的高度，这通常通过预处理过程完成，如上面的 `initializeHeight` 函数。一旦计算了高度，就可以直接调用 `lowestCommonAncestor` 函数寻找 LCA。