当前位置： 面试刷题>> 最近公共祖先 (经典算法题500道)
### 题目描述补充
**题目：最近公共祖先（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 示例代码
```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 示例代码
```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 示例代码
```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;
}
```
**码小课网站中有更多相关内容分享给大家学习**，包括但不限于算法基础、数据结构、面试技巧等，欢迎访问码小课网站深入学习。