[Python] 以Inorder Traversal 檢驗是否為BST

承襲上一回[Python] 實作Binary Tree，今天要介紹怎樣確認Tree是一個Binary Search Tree．
定義上的Binary Search Tree(BST):

• 左邊子樹的值都小於node的值
• 右邊子樹的值都小於node的值
• 左右的子樹都必須是BST

一開始依照定義寫了

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

class Solution(object):
    def isValidBST(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """
        if not root:
            return True

        if not root.right and not root.left:
            return True

        self.res = True      

        self.validation(root)
        return self.res

    def validation(self, root):


        if root.left:
            if root.left.val < root.val:
                self.min = root.left.val
                self.validation(root.left)
            else:
                self.res=False

        if root.right :
            if root.right.val > root.val:
                self.max = root.right.val
                self.validation(root.right)
            else:
                self.res=False

去分別判斷是不是每個左邊/右邊的子節點的值都小於/大於父節點，但是這樣的寫法無法判斷左子樹和右子數之間的節點大小．試了幾種寫法都不太成功，後來突然想到，如果一個數是BST那麼節點順序在inorder 走訪時（請參考[Python] 實作BST的走訪）順序一定是由小到大，所以改成下面這種更簡單易懂的寫法：

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

class Solution(object):
    def isValidBST(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """

        self.res = list()
        self.validation(root)

        return self.res == sorted(self.res) and len(set(self.res)) == len(self.res)
        #檢驗走訪的順序是否於排序完的順序相同，並且透過set的長度來排除兩個節點的值相同的情況

    def validation(self, root):

        if not root:
            return 
        else:
            self.validation(root.left)
            self.res.append(root.val)
            self.validation(root.right)