2015年10月25日 星期日

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

enter image description here
承襲上一回[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)