题目描述补充
题目:最近公共祖先(Lowest Common Ancestor, LCA)
在一棵给定的二叉树中,找到两个指定节点的最近公共祖先。在二叉树中,最近公共祖先的定义为:“对于有根树 T 的两个节点 p 和 q,最近公共祖先表示为一个节点 x,满足 x 是 p、q 的祖先且 x 的深度尽可能大(一个节点也可以是它自己的祖先)。”
输入:
- 一个二叉树的根节点
root
- 两个节点的值
p
和q
输出:
- 这两个节点的最近公共祖先节点的值
注意:
- 所有节点的值都是唯一的。
- 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;
}
}
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;
}
码小课网站中有更多相关内容分享给大家学习,包括但不限于算法基础、数据结构、面试技巧等,欢迎访问码小课网站深入学习。