leetcode235 二叉搜尋樹的最近公共祖先

思路：利用二叉搜尋樹左子樹中所有結點值小于根結點值，右子樹中所有結點值大于根結點值的性質。

是以，公共祖先就是最近的一左一右的情況，代碼很好了解。

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

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        while True:
            if root.val==p.val or root.val==q.val:#如果根結點就是某一個結點
                return root
            elif p.val<root.val<q.val or q.val<root.val<p.val:#如果滿足一左一右
                return root
            elif p.val<root.val:#都在左子樹
                root=root.left
            elif p.val>root.val:#都在右子樹
                root=root.right