# 二叉树的最近公共祖先 Lowest Common Ancestor of a Binary Tree

Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.

According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”

Given the following binary tree: root = [3,5,1,6,2,0,8,null,null,7,4]

img

```输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1

```输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4

• 所有节点的值都是唯一的。
• p、q 为不同节点且均存在于给定的二叉树中。

Note:

• All of the nodes' values will be unique.
• p and q are different and both values will exist in the binary tree.

### 解题思路：

• 如果在 node 的左子树没找到与 p，q 相等的结点，递归函数返回null，公共祖先在右侧结点
• 如果在 node 的右子树没找到与 p，q 相等的结点，递归函数返回null，公共祖先在左侧结点
• 如果在 node 左右子树都找到与 p，q 相等的结点，递归函数返回公众祖先 node 结点

### Java：

```class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
// 基线条件
if (root == null || root == p || root == q)
return root;
// 最小公共结点在左子树或右子树的情况
TreeNode leftNode = lowestCommonAncestor(root.left, p, q);
TreeNode rightNode = lowestCommonAncestor(root.right, p, q);
// 左子树或右子树未找到与 p，q 相等的结点时最小公共祖先在另一侧
if (leftNode == null)
return rightNode;
if (rightNode == null)
return leftNode;

return root;
}
}```

### Python：

```class Solution:
def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
if not root or root.val == p.val or root.val == q.val:
return root
left_node = self.lowestCommonAncestor(root.left, p, q)
right_node = self.lowestCommonAncestor(root.right, p, q)

if not left_node:
return right_node
if not right_node:
return left_node

return root```

### Golang：

```func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
if root == nil || root.Val == p.Val || root.Val == q.Val {
return root
}
leftNode := lowestCommonAncestor(root.Left, p, q)
rightNode := lowestCommonAncestor(root.Right, p, q)

if leftNode == nil {
return rightNode
}
if rightNode == nil {
return leftNode
}
return root
}```

0 条评论

• ### 【LeetCode 236.二叉树的最近公共祖先】双解法：递归实现 + 利用父指针

这题相较于 LeetCode 235.二叉搜索树的最近公共祖先 的递归思考起来比较有难度。

• ### 235. Lowest Common Ancestor of a Binary Search Tree(Tree-Easy)

Given a binary search tree (BST), find the lowest common ancestor (LCA) of two g...

• ### ​LeetCode刷题实战235：二叉搜索树的最近公共祖先

算法的重要性，我就不多说了吧，想去大厂，就必须要经过基础知识和业务逻辑面试+算法面试。所以，为了提高大家的算法能力，这个公众号后续每天带大家做一道算法题，题目就...

• ### Js算法与数据结构拾萃（4）：二叉树

因此只要答对这道题，你就可以超越世界级大牛，问鼎码林之巅（逃） 导读： •二叉树知识重点•二叉树深度不一，因此天生适用递归，因此可用递归处理•判断两树相等•翻转...

• ### Leetcode 235. Lowest Common Ancestor of a Binary Search Tree

Given a binary search tree (BST), find the lowest common ancestor (LCA) of two ...

• ### 【LeetCode 235.二叉搜索树的最近公共祖先】JavaScript/C++实现

例如，给定如下二叉搜索树: root = [6,2,8,0,4,7,9,null,null,3,5]

• ### LeetCode笔记：235. Lowest Common Ancestor of a Binary Search Tree

image.png For example, the lowest common ancestor (LCA) of nodes 2 and 8 is 6. A...

• ### 【LeetCode】235. Lowest Common Ancestor of a Binary Search Tree 公共祖先

Given a binary search tree (BST), find the lowest common ancestor (LCA) of two g...

• ### GitHub高星！互联网公司最常见的面试算法题大集合

LeetCode是一个美国的在线编程网站，收集了各个大厂的笔试面试题，对找工作的毕业生和开发者来说，非常有价值。不过LeetCode上面的题目很多都是考察应聘者...

• ### Tree - 235. Lowest Common Ancestor of a Binary Search Tree

235. Lowest Common Ancestor of a Binary Search Tree

• ### Leetcode 236. Lowest Common Ancestor of a Binary Tree

根据LCA的定义，二叉树中最小公共祖先就是两个节点p和q最近的共同祖先节点，LCA的定义没什么好解释的，主要是这道题的解法。 　　我们要找p和q的最小公共...

• ### 【Leetcode235】关关的刷题日记66 –Lowest Common Ancestor of a BST

关关的刷题日记66 – Leetcode 235 Lowest Common Ancestor of a Binary Search Tree 题目 ? 题目的...

• ### 二叉树-LeetCode 235、236、226、230（中序，LCA，DFS）

给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。 百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 ...

• ### 二叉树-最近的公共祖先

已知二叉树，求二叉树中给定的两个节点的最近公共祖先。 最近公共祖先: 两节点v与w的最近公共祖先u，满足在树上最低(离根最 远)，且v,w两个节点都是u的子孙。...

• ### 资源 | 从算法到数据结构，百道面试问题实现答案集合

选自GitHub 作者：Sherali Obidov 机器之心编译 参与：李亚洲、微胖、蒋思源 该资源是算法、数据结构以及面试问题解决方案的集合，里面的 rep...

• ### Leetcode 236. Lowest Common Ancestor of a Binary Tree

Given a binary tree, find the lowest common ancestor (LCA) of two given nodes i...

• ### leetcode树之二叉搜索树的最近公共祖先

这里采用递归的思路，并利用二叉搜索树的特性来解题；针对root.val大于p.val及q.val的递归执行lowestCommonAncestor(root.l...

• ### Tree - 236. Lowest Common Ancestor of a Binary Tree

236. Lowest Common Ancestor of a Binary Tree

• ### 【leetcode刷题】T131-二叉搜索树的最近公共祖先

https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-search-tree/