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

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

示例 1：

?

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

示例 2：

?

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

示例 3：

輸入：root = [1,2], p = 1, q = 2 輸出：1

提示：

• 樹中節(jié)點(diǎn)數(shù)目在范圍 [2, 105] 內(nèi)。
• -109 <= Node.val <= 109
• 所有 Node.val 互不相同
• p != q
• p 和 q 均存在于給定的二叉樹中。

遞歸解法

class Solution:def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':if root==None or root==p or root==q:return rootleft = self.lowestCommonAncestor(root.left,p,q)right = self.lowestCommonAncestor(root.right,p,q)if left==None:return rightelif right==None:return leftreturn root

總結(jié)

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

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