@@ -0,0 +1,2440 @@
+# -*-coding:utf-8-*-%0A%0A%0A%22%22%22%0AQuestion:%0A    Lowest Common Ancestor of a Binary Search Tree%0A%0A    Given a binary search tree (BST), find the lowest common ancestor (LCA) of two given nodes in the BST.%0A%0A    According to the definition of LCA on Wikipedia: %E2%80%9CThe lowest common ancestor is defined between two nodes v and w as the lowest node in T that has both v and w as descendants (where we allow a node to be a descendant of itself).%E2%80%9D%0A%0A            _______6______%0A           /              %5C%0A        ___2__          ___8__%0A       /      %5C        /      %5C%0A       0      _4       7       9%0A             /  %5C%0A             3   5%0A    For example, the lowest common ancestor (LCA) of nodes 2 and 8 is 6. Another example is LCA of nodes 2 and 4 is 2, since a node can be a descendant of itself according to the LCA definition.%0A%0APerformance:%0A    1. Total Accepted: 28843 Total Submissions: 75868 Difficulty: Easy%0A    2. Your runtime beats 7.19%25 of python submissions.%0A%22%22%22%0A%0A%0A# Definition for a binary tree node.%0Aclass TreeNode(object):%0A    def __init__(self, x):%0A        self.val = x%0A        self.left = None%0A        self.right = None%0A%0Aclass Solution(object):%0A    %22%22%22%0A    The main idea is figure out to using the order of nodes values.%0A%0A    Getting ideas from http://www.geeksforgeeks.org/lowest-common-ancestor-in-a-binary-search-tree/%0A    1. Get the finding a node idea first. Wrong, cause there still no back way to find the sequence.%0A    2. It's a binary search tree, left is smaller than right. It's the key.%0A    %22%22%22%0A    def lowestCommonAncestor(self, root, p, q):%0A        %22%22%22%0A        :type root: TreeNode%0A        :type p: TreeNode%0A        :type q: TreeNode%0A        :rtype: TreeNode%0A        %22%22%22%0A        # cause root is already the highest.%0A        if p.val %3C= root.val %3C= q.val or q.val %3C= root.val %3C= p.val:%0A            return root%0A%0A        if p.val %3C root.val and q.val %3C root.val:%0A            return self.lowestCommonAncestor(root.left, p, q)%0A        if p.val %3E root.val and q.val %3E root.val:%0A            return self.lowestCommonAncestor(root.right, p, q)%0A%0An0 = TreeNode(0)%0An2 = TreeNode(2)%0An3 = TreeNode(3)%0An4 = TreeNode(4)%0An5 = TreeNode(5)%0An6 = TreeNode(6)%0An7 = TreeNode(7)%0An8 = TreeNode(8)%0An9 = TreeNode(9)%0An6.left = n2%0An6.right = n8%0An2.left = n0%0An2.right = n4%0An8.left = n7%0An8.right = n9%0An4.left = n3%0An4.right = n5%0An2.left = n0%0A%0Aassert Solution().lowestCommonAncestor(n6, n2, n8) is n6%0Aassert Solution().lowestCommonAncestor(n6, n2, n4) is n2%0A

Add 236-lowest-common-ancestor-of-a-binary-search-tree.py