树：力扣235. 二叉搜索树的最近公共祖先

1、题目描述：

2、题解：

方法1：递归 核心思想：p和 q其中的一个在 LCA 节点的左子树上，另一个在 LCA 节点的右子树上。LCA最近公共祖先 算法:

先看p,q结点是否在根结点的右侧，然后在右侧递归找LCA 否则，看p,q结点是否在根结点的左侧，然后在左侧递归找LCA 否则，找到LCA，返回

代码如下：

# 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 = root.val pval = p.val qval = q.val if pval > parent and qval > parent: return self.lowestCommonAncestor(root.right,p,q) elif pval < parent and qval < parent: return self.lowestCommonAncestor(root.left,p,q) else: return root

方法2：迭代 核心思想：同上 算法：

循环体内： 如果p,q结点在右侧，就在右侧找 否则，如果p,q结点在左侧，就在左侧找 否则，说明p,q在此结点的两边，找到LCA

代码如下：

# 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': #非递归 pval = p.val qval = q.val node = root while node: parent = node.val if pval > parent and qval > parent: node = node.right elif pval < parent and qval < parent: node = node.left else: return node

3、复杂度分析：

方法1： 时间复杂度：O(N) 空间复杂度：O(N) 方法2： 时间复杂度：O(N) 空间复杂度：O(1)