題目鏈接： https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-tree

難度：中等

通過率：57.2%

題目描述:

給定一個二叉樹, 找到該樹中兩個指定節(jié)點的最近公共祖先。

百度百科中最近公共祖先的定義為："對于有根樹 T 的兩個結(jié)點 p、q，最近公共祖先表示為一個結(jié)點 x，滿足 x 是 p、q 的祖先且 x 的深度盡可能大（ 一個節(jié)點也可以是它自己的祖先 ）。"

例如，給定如下二叉樹: root = [3,5,1,6,2,0,8,null,null,7,4]

示例:

示例 1:

輸入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1 輸出: 3 解釋: 節(jié)點 5 和節(jié)點 1 的最近公共祖先是節(jié)點 3。

示例 2:

輸入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4 輸出: 5 解釋: 節(jié)點 5 和節(jié)點 4 的最近公共祖先是節(jié)點 5。因為根據(jù)定義最近公共祖先節(jié)點可以為節(jié)點本身。

說明:

• 所有節(jié)點的值都是唯一的。
• p、q 為不同節(jié)點且均存在于給定的二叉樹中。

思路:

相關題型：235. 二叉搜索樹的最近公共祖先

class Solution:def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':if root in {None, p, q}: return rootleft = self.lowestCommonAncestor(root.left, p, q)right = self.lowestCommonAncestor(root.right, p, q)if left and right:return rootreturn left or right

更多題解：

九四干：[LeetCode] 題目匯總(持續(xù)更新)?zhuanlan.zhihu.com

總結(jié)

以上是生活随笔為你收集整理的最近公共祖先_[LeetCode] 236. 二叉树的最近公共祖先的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。