700. Search in a Binary Search Tree

"""
用Iteration的方法来求出sorted array， 然后用binary search去找到值
"""

class Solution(object):
    def inorder(self, root, ls):
        st = []
        while st or root:
            if root:
                st.append(root)
                root = root.left
            else:
                root = st.pop()
                ls.append(root)
                root = root.right

    def searchBST(self, root, val):
        """
        :type root: TreeNode
        :type val: int
        :rtype: TreeNode
        """
        ls = []
        self.inorder(root, ls)

        l = 0
        r = len(ls)-1
        while l <= r:
            mid = l + (r - l) // 2
            if val < ls[mid].val:
                r = mid - 1
            elif val == ls[mid].val:
                return ls[mid]
            else:
                l = mid + 1

        return None