LeetCode.jpg
二叉搜索樹的最近公共祖先
給定一個二叉搜索樹, 找到該樹中兩個指定節(jié)點的最近公共祖先驰坊。
百度百科中最近公共祖先的定義為：“對于有根樹 T 的兩個結(jié)點 p拣帽、q，最近公共祖先表示為一個結(jié)點 x，滿足 x 是 p伟阔、q 的祖先且 x 的深度盡可能大（一個節(jié)點也可以是它自己的祖先）愈魏∶俨＃”
例如想际，給定如下二叉搜索樹: root = [6,2,8,0,4,7,9,null,null,3,5]
image
示例 1:
輸入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
輸出: 6
解釋: 節(jié)點 2 和節(jié)點 8 的最近公共祖先是 6。
示例 2:
輸入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
輸出: 2
解釋: 節(jié)點 2 和節(jié)點 4 的最近公共祖先是 2, 因為根據(jù)定義最近公共祖先節(jié)點可以為節(jié)點本身溪厘。
說明:
所有節(jié)點的值都是唯一的胡本。
p、q 為不同節(jié)點且均存在于給定的二叉搜索樹中畸悬。
Python3實現(xiàn)
遞歸
#@author:leacoder
#@des: 遞歸, 二叉搜索樹的最近公共祖先
# 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 p.val<root.val and q.val<root.val: #如果 p q 的值都是小于root的值 那么 需要在二叉搜索樹 左子樹中找
return self.lowestCommonAncestor(root.left,p,q)
if p.val>root.val and q.val>root.val: #如果 p q 的值都是大于root的值 那么 需要在二叉搜索樹 右子樹中找
return self.lowestCommonAncestor(root.right,p,q)
return root #其他情況 一個比root 大 一個比root小 那么 root必然為其公共祖先
循環(huán)
#@author:leacoder
#@des: 循環(huán), 二叉搜索樹的最近公共祖先
# 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':
while root:
if p.val<root.val and q.val<root.val: #如果 p q 的值都是小于root的值 那么公共祖先必在其左子樹中
root = root.left
elif p.val>root.val and q.val>root.val: #如果 p q 的值都是大于root的值 那么公共祖先必在其右子樹中
root = root.right
else:
return root
GitHub鏈接：
https://github.com/lichangke/LeetCode
知乎個人首頁：
https://www.zhihu.com/people/lichangke/
個人Blog:
https://lichangke.github.io/
歡迎大家來一起交流學(xué)習(xí)
