Lowest Common Ancestor of a BST

因为是BST，我们是可以利用二分的性质缩小时间复杂度的，最朴素的想法自然是分别两次搜索记录p和q对应的路径，最后拿出来比较最后的共同点在哪里

class Solution(object):
    def lowestCommonAncestor(self, root, p, q):
        """
        :type root: TreeNode
        :type p: TreeNode
        :type q: TreeNode
        :rtype: TreeNode
        """
        pList, qList = [], []
        self.helper(root, pList, p)
        self.helper(root, qList, q)
        lastCommon = None

        for i in xrange(min(len(pList), len(qList))):
            if qList[i].val != pList[i].val:
                break
            lastCommon = qList[i]

        return lastCommon

    def helper(self, root, nodes, target):
        if root == target:
            nodes.append(root)
            return

        nodes.append(root)
        if root.val < target.val:
            self.helper(root.right, nodes, target)
        else:
            self.helper(root.left, nodes, target)

但是明显可以看到，如果一个root值导致我们必须在p，q两个搜索里面分叉时，这个root就已经肯定是他们的LCA了，基于这个原理就有更简单iterative代码，同时这种方法也是O(1)空间的

class Solution(object):
    def lowestCommonAncestor(self, root, p, q):
        """
        :type root: TreeNode
        :type p: TreeNode
        :type q: TreeNode
        :rtype: TreeNode
        """
        while root:
            if p.val < root.val > q.val:
                root = root.left
            elif p.val > root.val < q.val:
                root = root.right
            else:
                return root
        return None

Lowest Common Ancestor of a Binary Tree

还是最朴素的办法，收集两个list再逐个比对

class Solution(object):
    def lowestCommonAncestor(self, root, p, q):
        """
        :type root: TreeNode
        :type p: TreeNode
        :type q: TreeNode
        :rtype: TreeNode
        """
        pList, qList = [], []
        self.helper(root, p, [], pList)
        self.helper(root, q, [], qList)

        lastCommon = None
        for i in xrange(min(len(pList[0]), len(qList[0]))):
            if pList[0][i] != qList[0][i]:
                return lastCommon
            lastCommon = qList[0][i]
        return lastCommon

    def helper(self, root, target, tmp, res):
        if not root:
            return 

        if root == target:
            tmp.append(root)
            res.append(tmp[:])
            tmp.pop()
            return 

        tmp.append(root)
        self.helper(root.left, target, tmp, res)
        self.helper(root.right, target, tmp, res)
        tmp.pop()
        return

这道题的简单递归版不是很好理解，暂时先不看