【面试-leetcode236】查找二叉树公共祖先（递归+迭代）

这是 leetcode 面试刷题一题多解系列的第11篇，练习分别使用递归和迭代的方式查找二叉树的最近公共祖先。

题目

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

来源：力扣（LeetCode）
链接：leetcode.cn/problems/lo…
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题解1—递归

对于每个节点，可以通过递归的方式来寻找它的左右子树中是否存在 p 和 q。递归的结束条件有以下三种情况：

1. 当前节点为空，返回 null。
2. 当前节点等于 p 或 q，直接返回当前节点。
3. 左右子树中分别存在 p 和 q，当前节点即为它们的最近公共祖先。

递归代码如下：

var lowestCommonAncestor = function(root, p, q) {
    if (root === null || root === p || root === q) {
        return root;
    }
    let left = lowestCommonAncestor(root.left, p, q);
    let right = lowestCommonAncestor(root.right, p, q);
    if (left !== null && right !== null) {
        return root;
    }
    return left !== null ? left : right;
};

题解2—迭代

除了递归，我们还可以使用迭代的方式来解决二叉树最近公共祖先问题。迭代的思路是使用栈来模拟递归的过程，具体步骤如下：

1. 初始化栈，并将根节点和它的父节点分别入栈。
2. 当栈不为空时，取出栈顶元素。
3. 如果该节点的左右子树都已经访问过，或者该节点是 p 或 q 中的一个，就返回该节点。
4. 否则，将该节点的左右子树以及它们的父节点分别入栈。

迭代代码如下：

var lowestCommonAncestor = function(root, p, q) {
    let stack = [root];
    let parent = new Map();
    parent.set(root, null);
    while (!parent.has(p) || !parent.has(q)) {
        let node = stack.pop();
        if (node.left !== null) {
            parent.set(node.left, node);
            stack.push(node.left);
        }
        if (node.right !== null) {
            parent.set(node.right, node);
            stack.push(node.right);
        }
    }
    let ancestors = new Set();
    while (p !== null) {
        ancestors.add(p);
        p = parent.get(p);
    }
    while (!ancestors.has(q)) {
        q = parent.get(q);
    }
    return q;
};

本文介绍了两种解决二叉树最近公共祖先问题的方法：递归和迭代。递归的思路是根据题目的性质递归的思路是根据题目的性质，不断地将问题拆分为子问题，直到达到结束条件。而迭代则是使用栈来模拟递归的过程，通过遍历整个二叉树，寻找最近公共祖先节点。

在实际应用中，递归的代码更简洁易懂，但在处理大规模数据时可能会导致栈溢出，而迭代则可以更好地处理大规模数据。因此，在实际应用中，需要根据具体的问题场景来选择合适的解决方案。

我的更多前端资讯

欢迎大家技术交流 资料分享 摸鱼 求助皆可 —[链接](