【代码随想录day21】二叉搜索树的最近公共祖先

题目 

 

 思路

解题的关键是知道自顶向低递归遍历，第一次遇到root在p和q的区间中时，则root就是p和q的最近公共祖先节点。 

递归法 

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = Noneclass Solution:def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':if not root:return if root.val>p.val and root.val>q.val:left = self.lowestCommonAncestor(root.left, p, q)if left:return leftif root.val<p.val and root.val<q.val:right = self.lowestCommonAncestor(root.right, p, q)if right:return rightreturn root

迭代法

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = Noneclass Solution:def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':while root:if root.val>p.val and root.val>q.val:root = root.leftelif root.val<p.val and root.val<q.val:root = root.rightelse:return root