235. Lowest Common Ancestor of a Binary Search Tree

235. Lowest Common Ancestor of a Binary Search Tree

• 如果大于最大值，则所求在左子树，如果小于最小值，则所求在右子树，否则，返回当前节点

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

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

    #递归
    def lowestCommonAncestor(self, root, p, q):
        """
        :type root: TreeNode
        :type p: TreeNode
        :type q: TreeNode
        :rtype: TreeNode
        """
        if root.val > max(p.val, q.val):
            return self.lowestCommonAncestor(root.left, p, q)
        elif root.val < min(p.val, q.val):
            return self.lowestCommonAncestor(root.right, p, q)
        else:
            return root

    #找路径后比较
    def lowestCommonAncestor(self, root, p, q):
        """
        :type root: TreeNode
        :type p: TreeNode
        :type q: TreeNode
        :rtype: TreeNode
        """
        l1 = self.findPath(root, p)
        l2 = self.findPath(root, q)
        res = root
        for i in range(min(len(l1), len(l2))):
            if l1[i] == l2[I]:
                res = l1[I]
            else:
                break
        return res
    
    def findPath(self, root, p):
        res = []
        while root.val != p.val:
            res.append(root)
            if root.val > p.val:
                root = root.left
            else:
                root = root.right
        res.append(p)
        return res

---

236. Lowest Common Ancestor of a Binary Tree

236. Lowest Common Ancestor of a Binary Tree

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def lowestCommonAncestor(self, root, p, q):
        """
        :type root: TreeNode
        :type p: TreeNode
        :type q: TreeNode
        :rtype: TreeNode
        """
        mydic = {}
        l1 = self.findPath(root, p)
        l2 = self.findPath(root, q)
        res = root
        for i in range(min(len(l1), len(l2))):
            if l1[i] == l2[I]:
                res = l1[I]
            else:
                break
        return res

    def findPath(self, root, p):
        res = []
        mydic = {}
        qu = [root]
        while qu:
            node = qu.pop(0)
            if node == p:
                break
            else:
                if node.left:
                    qu.append(node.left)
                    mydic[node.left] = node
                if node.right:
                    qu.append(node.right)
                    mydic[node.right] = node
        while node != root:
            res.append(node)
            node = mydic[node]
        res.append(root)
        return res[::-1]