Study Plan For Algorithms - Part41

1. 二叉搜索树的最近公共祖先
给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。
方法一：

class TreeNode:def __init__(self, val=0, left=None, right=None):self.val = valself.left = leftself.right = rightdef lowestCommonAncestor(root, p, q):if p.val > q.val:temp = pp = qq = tempwhile root is not None:if root.val < p.val:root = root.rightelif root.val > q.val:root = root.leftelse:breakreturn root

方法二：

class TreeNode:def __init__(self, val=0, left=None, right=None):self.val = valself.left = leftself.right = rightdef lowestCommonAncestor(root, p, q):if root.val < p.val and root.val < q.val:return lowestCommonAncestor(root.right, p, q)if root.val > p.val and root.val > q.val:return lowestCommonAncestor(root.left, p, q)return root