2019-08-26 LeetCode235. 二叉搜索树的最近

10min，主要问题是p不一定小于q

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        small=min(p.val,q.val)
        big=max(p.val,q.val)
        return self.dfs(root,small,big)


    def dfs(self, root: 'TreeNode',small,big):
        if root.val>=small and root.val<=big:return root
        if root.val>small and root.val>big:return self.dfs(root.left,small,big)
        if root.val<small and root.val<big:return self.dfs(root.right,small,big)

迭代法，不使用递归

class Solution2:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        cur=root
        while cur!=None:
            if p.val < cur.val and q.val < cur.val:
                cur = cur.left
            elif p.val > cur.val and q.val > cur.val:
                cur = cur.right
            else:
                return cur