###### tags: `Leetcode` `medium` `tree` `python`

# 235. Lowest Common Ancestor of a Binary Search Tree

## [題目連結:] https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-search-tree/

## 題目:
Given a binary search tree (BST), find the lowest common ancestor (LCA) node of two given nodes in the BST.

According to the ```definition of LCA on Wikipedia```: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both ```p and q``` as descendants (where we allow **a node to be a descendant of itself**).”


#### [圖片來源:] https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-search-tree/

## 解題想法:
* 題目為: 給定兩node，p、q，求他們最近的共同祖先
* 此數為Binary Search Tree:
* 左子一定比root.val小
* 右子一定比root.val大
* 遞迴判斷當前root.val與p.val,q.val之關係
* 若root.val大於 p.val、q.val
* 代表祖先要往root.left小的地方靠近
* 若root.val小於 p.val、q.val
* 代表祖先要往root.right大的地方靠近

## Python:

#Definition for a binary tree node.
class TreeNode(object):
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
    def insertLeft(self,node):
        if self.left == None:
            self.left = TreeNode(node)
        else:
            self.left.insertLeft(node)
    def insertRight(self,node):
        if self.right == None:
            self.right = TreeNode(node)
        else:
            self.right.insertRight(node)
    def printTree(self):
        ans = []
        stack = []
        stack.append(self)
        flag = 1
        while stack:
            root = stack.pop(0)
            if flag == 1:
                ans.append(root.val)
                flag = 0
            if root.left :
                ans.append(root.left.val)
                stack.append(root.left)
            if root.right:
                ans.append(root.right.val)
                stack.append(root.right)
        print(ans,'\n')
             
class Solution(object):
    def lowestCommonAncestor(self, root, p, q):
        """
        :type root: TreeNode
        :type p: TreeNode
        :type q: TreeNode
        :rtype: TreeNode
        """
        if root.val>p.val and root.val>q.val:
            return self.lowestCommonAncestor(root.left,p,q)
        elif root.val<p.val and root.val<q.val:
            return self.lowestCommonAncestor(root.right,p,q)
        else:
            return root
    
if __name__ == '__main__':
    root = TreeNode(6)
    root.insertLeft(2)
    root.insertRight(8)
    root.left.insertLeft(0)
    root.left.insertRight(4)
    root.right.insertLeft(7)
    root.right.insertRight(9)
    root.left.right.insertLeft(3)
    root.left.right.insertRight(5)
    root.printTree()

    p = root.left
    q = root.left.right
    result = Solution()
    ans = result.lowestCommonAncestor(root,p,q)
    print(ans.val)