二叉樹的最近公共祖先
題目描述
給定一個(gè)二叉樹, 找到該樹中兩個(gè)指定節(jié)點(diǎn)的最近公共祖先讼撒。
百度百科中最近公共祖先的定義為：“對(duì)于有根樹 T 的兩個(gè)結(jié)點(diǎn) p、q椒惨，最近公共祖先表示為一個(gè)結(jié)點(diǎn) x系洛，滿足 x 是 p、q 的祖先且 x 的深度盡可能大（一個(gè)節(jié)點(diǎn)也可以是它自己的祖先）蝇狼。”
例如欣硼，給定如下二叉樹: 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é)點(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)本身诈胜。
來(lái)源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-tree
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有豹障。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處焦匈。
解題思路
使用遞歸
# 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 root is None: return root
if root == p or root == q:return root
left = self.lowestCommonAncestor(root.left,p,q)
right = self.lowestCommonAncestor(root.right,p,q)
if left and right :return root
if not left : return right
if not right: return left
return None
如果是二叉搜索樹的最近公共祖先血公，那么可以利用二叉搜索樹的性質(zhì)左兒子都比根節(jié)點(diǎn)小，右兒子都比根節(jié)點(diǎn)大缓熟，來(lái)減少遞歸的次數(shù)累魔，加快運(yùn)算結(jié)果。
# 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':
parent_val=root.val
p_val=p.val
q_val=q.val
if p_val<parent_val and q_val<parent_val:
return self.lowestCommonAncestor(root.left,p,q)
elif p_val>parent_val and q_val>parent_val:
return self.lowestCommonAncestor(root.right,p,q)
else:
return root
