二叉樹與二叉搜索樹的公共祖先 力扣 （Python）

二叉樹與二叉搜索樹的公共祖先 力扣

• • 236. 二叉樹的最近公共祖先
  • 235. 二叉搜索樹的最近公共祖先

236. 二叉樹的最近公共祖先

解題思路：
判斷二叉樹的公共祖先由以下三種情況組成。

# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
if not root:
return None
if root is p or root is q: return root
left = self.lowestCommonAncestor(root.left, p, q)
right = self.lowestCommonAncestor(root.right, p, q)
#情況1， 如果 p, q 在左右子樹中，返回當前節點
if left and right:
return root
#情況2， 如果 p, q 都不在左右子樹中，返回空
if left is None and right is None:
return None
#情況3， 如果p, q 只有一個存在於root為根的節點中，返回當前節點
return right if left is None else left

235. 二叉搜索樹的最近公共祖先

解題思路：
當考慮二叉搜索樹的公共祖先時，要結合二叉搜索樹的性質。

class Solution:
def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
#當前節點大於 p, q 去左子樹尋找
if p.val < root.val and q.val < root.val:
return self.lowestCommonAncestor(root.left, p ,q)
#當前節點小於 p, q 去右子樹尋找
elif p.val > root.val and q.val > root.val:
return self.lowestCommonAncestor(root.right, p ,q)
#返回當前節點
else:
return root

以上的兩題均可以用以下方式解決。

二叉搜索樹其實是特殊的二叉樹。

而對於二叉樹的最小公共祖先來說，以下代碼包含了問題一的三種判斷情況。

class Solution:
def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
if not root or root is p or root is q:
return root
left = self.lowestCommonAncestor(root.left, p, q)
right = self.lowestCommonAncestor(root.right, p , q)
#包含問題一二叉樹的三種情況
if not left:
return right
if not right:
return left
return root