今天的目標是判斷一個二元搜尋樹是否合法？(Hackerrank 上的 Is this a Binary Search Tree ? )

二元搜尋樹不同於二元樹的地方是：
二元搜尋樹的構造須根據資料內容來放置，即根節點資料大於左子樹的任意節點資料，且小於右子樹的任意節點資料

那我們就直接從定義下手這個函式實作！
大概的想法是我們不斷縮小 root.data 的合法範圍，再搭配遞迴將二元樹分成無數個子樹！

def check_binary_search_tree_(root):
    return helper(root, float("-inf"), float("inf"))

def helper(root, _min, _max):
    if root is None:
        return True
    if root.data <= _min or root.data >= _max: #invalid
        return False
    # 分割成左、右子樹
    return helper(root.left, _min, root.data) & helper(root.right, root.data, _max)

第二種方式是利用之前學過的 Inorder Traversal 來實作
因為二元搜尋樹使用 Inorder Traversal 得出的結果恰好是一串嚴格遞增的數

def check_binary_search_tree_(root):
    temp = []
    helper(root, temp)
    for i in range(1, len(temp)):
        if temp[i] <= temp[i-1]:
            return False
    return True
    
def helper(root, temp): # inorder traversal
    if root is None:
        return None
    if root.left != None:
        helper(root.left, temp)
    temp.append(root.data)
    if root.right != None:
        helper(root.right, temp)

沒想到這個題目也可以這麼有趣吧！