当前位置: 面试刷题>> 最近公共祖先 (经典算法题500道)


题目描述补充

题目:最近公共祖先(Lowest Common Ancestor, LCA)

在一棵给定的二叉树中,找到两个指定节点的最近公共祖先。在二叉树中,最近公共祖先的定义为:“对于有根树 T 的两个节点 p 和 q,最近公共祖先表示为一个节点 x,满足 x 是 p、q 的祖先且 x 的深度尽可能大(一个节点也可以是它自己的祖先)。”

输入

  • 一个二叉树的根节点 root
  • 两个节点的值 pq

输出

  • 这两个节点的最近公共祖先节点的值

注意

  • 所有节点的值都是唯一的。
  • p、q 为树中的节点。

示例

给定如下的二叉树:

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

对于节点 p = 5q = 1,LCA 是节点 3

对于节点 p = 5q = 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;
    }
}

function lowestCommonAncestor($root, $p, $q) {
    if ($root == null || $root->val == $p || $root->val == $q) {
        return $root;
    }

    $left = lowestCommonAncestor($root->left, $p, $q);
    $right = 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

def lowestCommonAncestor(root, p, q):
    if root is None or root.val == p or root.val == q:
        return root
    
    left = lowestCommonAncestor(root.left, p, q)
    right = 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)
}

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

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

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

    return left || right;
}

码小课网站中有更多相关内容分享给大家学习,包括但不限于算法基础、数据结构、面试技巧等,欢迎访问码小课网站深入学习。

推荐面试题