一、235. 二叉搜索树的最近公共祖先

1.1、题目描述

1.2、题解

1.2.1、直接查找

class Solution: def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode': #确保 p < q if p.val > q.val: p,q = q,p while root: if root.val > q.val: # q为较大值， 节点的值表q.val还大，说明p,q都在节点的左侧（节点 N 左子树上的所有节点的值都小于等于节点 N 的值） root = root.left elif root.val < p.val: root = root.right else: return root

1.2.2、递归

class Solution: def lowestCommonAncestor(self, root, p, q): parent_val = root.val p_val = p.val q_val = q.val if p_val > q_val: p_val, q_val = q_val, p_val if p_val > parent_val: return self.lowestCommonAncestor(root.right, p, q) elif q_val < parent_val: return self.lowestCommonAncestor(root.left, p, q) else: return root

二、236. 二叉树的最近公共祖先