题目描述

给定一棵二叉树，以及这棵树上的两个节点 p 和 q，找到 p 和 q 的最近公共祖先（Lowest Common Ancestor, LCA）。

最近公共祖先的定义为：“对于有根树 T 的两个节点 p 和 q，最近公共祖先表示为一个节点 x，在树中满足以下条件：

• x 是 p、q 的祖先节点
• x 的深度尽可能大（即，距离根最远）”

注意：

• 树上的节点都不相同。
• p、q 为给定树中的不同节点且均存在于给定的树中。

示例

给定如下二叉树:

    3
   / \
  5   1
 / \ / \
6   2 0   8
   / \
  7   4

对于节点 p = 5 和 q = 1，LCA 是节点 3。

对于节点 p = 5 和 q = 4，LCA 是节点 5。

PHP 示例代码

class TreeNode {
    public $val;
    public $left;
    public $right;

    function __construct($val = 0, $left = null, $right = null) {
        $this->val = $val;
        $this->left = $left;
        $this->right = $right;
    }
}

class Solution {
    function lowestCommonAncestor($root, $p, $q) {
        if ($root === null || $root === $p || $root === $q) {
            return $root;
        }

        $left = $this->lowestCommonAncestor($root->left, $p, $q);
        $right = $this->lowestCommonAncestor($root->right, $p, $q);

        if ($left !== null && $right !== null) {
            return $root;
        }

        return ($left !== null) ? $left : $right;
    }
}

Python 示例代码

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        if root is None or root == p or root == q:
            return root

        left = self.lowestCommonAncestor(root.left, p, q)
        right = self.lowestCommonAncestor(root.right, p, q)

        if left and right:
            return root
        
        return left if left is not None else right

JavaScript 示例代码

function TreeNode(val, left, right) {
    this.val = (val===undefined ? 0 : val)
    this.left = (left===undefined ? null : left)
    this.right = (right===undefined ? null : right)
}

var Solution = function() {};

Solution.prototype.lowestCommonAncestor = function(root, p, q) {
    if (!root || root === p || root === q) {
        return root;
    }

    let left = this.lowestCommonAncestor(root.left, p, q);
    let right = this.lowestCommonAncestor(root.right, p, q);

    if (left && right) {
        return root;
    }

    return left ? left : right;
};

这些代码示例均展示了如何递归地寻找二叉树中两个节点的最近公共祖先。在面试中，除了给出代码，还可以讨论算法的时间复杂度和空间复杂度，以及如何优化这些代码。