###### tags: `Leetcode` `medium` `tree` `python` `Top 100 Liked Questions`

# 98. Validate Binary Search Tree

## [題目連結:]https://leetcode.com/problems/validate-binary-search-tree/

## 題目:
Given the ```root``` of a binary tree, determine if it is a valid binary search tree (BST).

A **valid BST** is defined as follows:

* he left subtree of a node contains only nodes with keys **less than** the node's key.
* The right subtree of a node contains only nodes with keys **greater than** the node's key.
* Both the left and right subtrees must also be binary search trees.


#### [圖片來源:] https://leetcode.com/problems/validate-binary-search-tree/

## 解題想法:
* 題目為，給定一tree，判斷是否為合法的BST:
* 左子一定要小於root.val
* 右子一定要大於root.val
* 左右子樹也要是BST

## Python: DFS

* 遞迴求解:
* 判斷當前root.val是否處於left.val、right.val之間

class TreeNode(object):
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
    def insertLeft(self,node):
        if self.left==None:
            self.left=TreeNode(node)
        else:
            self.left.insertLeft(node)
    def insertRight(self,node):
        if self.right==None:
            self.right=TreeNode(node)
        else:
            self.right.insertRight(node)
    def printTree(self):
        root=self
        stack=[root]
        res=[]
        while stack:
            root=stack.pop(0)
            res.append(root.val)
            if root.left:
                stack.append(root.left)
            if root.right:
                stack.append(root.right)
        print(res)
        
class Solution(object):
    def isValidBST(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """
        return self.dfs(root,float('-inf'),float('inf'))
    #判斷每點是否處於邊界值之間
    def dfs(self,root,minLimit,maxLimit):
        if not root:
            return True
        if minLimit<root.val<maxLimit:
            return self.dfs(root.left,minLimit,root.val) and self.dfs(root.right,root.val,maxLimit)
        else: #若不再界內
            return False

root=TreeNode(5)
root.insertLeft(1)
root.insertRight(4)
#root.right.insertLeft(3)
#root.right.insertRight(6)
root.printTree()

result = Solution()
ans = result.isValidBST(root)
print(ans)

## Python: Inorder
* 因為BST的inorder traversal一定為由小到大排序
* 額外設self.pre
* 紀錄當前節點的前一點，用以比較大小

* 示意流程:

ex: 
    5
  1   4

先進去inorder(5) pre=None
        ->跑 子inorder(1) pre=None
            ->跑完更新pre=1
    比較當前pre(1)<root5:
        True 合格
        pre更新為5
        ->跑子 inorder(4) pre=5
            ->跑到root4<=pre5:
                return False 不合格
=> final False

class TreeNode(object):
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
    def insertLeft(self,node):
        if self.left==None:
            self.left=TreeNode(node)
        else:
            self.left.insertLeft(node)
    def insertRight(self,node):
        if self.right==None:
            self.right=TreeNode(node)
        else:
            self.right.insertRight(node)
    def printTree(self):
        root=self
        stack=[root]
        res=[]
        while stack:
            root=stack.pop(0)
            res.append(root.val)
            if root.left:
                stack.append(root.left)
            if root.right:
                stack.append(root.right)
        print(res)

class Solution(object):
    def isValidBST(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """
        self.pre=None
        return self.inorder(root)
    #左(中)右
    def inorder(self,root):
        if not root:
            return True
        #遞歸左子
        if not self.inorder(root.left): 
            return False
        #判斷當前，若pre.val小於root.val: 正常case
        if self.pre==None or self.pre.val<root.val:
            self.pre=root #更新該root為下次比較的對象
            #遞歸右子
            return self.inorder(root.right)
        else:
            return False

root=TreeNode(5)
root.insertLeft(1)
root.insertRight(4)
#root.right.insertLeft(3)
#root.right.insertRight(6)
root.printTree()

result = Solution()
ans = result.isValidBST(root)
print(ans)