[Tree/BackTracking]98. Validate

• 分类：Tree/BackTracking
• 时间复杂度: O(n) 这种把树的节点都遍历一遍的情况时间复杂度为O(n)
• 空间复杂度: O(h) 树的节点的深度

98. Validate Binary Search Tree

Given a binary tree, determine if it is a valid binary search tree (BST).

Assume a BST is defined as follows:

• The 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.

Example 1:

Input:
    2
   / \
  1   3
Output: true

Example 2:

    5
   / \
  1   4
     / \
    3   6
Output: false
Explanation: The input is: [5,1,4,null,null,3,6]. The root node's value
             is 5 but its right child's value is 4.

代码：

方法1，限定子节点的范围

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

class Solution:
    def isValidBST(self, root: 'TreeNode') -> 'bool':
        
        if root==None:
            return True
        
        return self.helper(root,float('-inf'),float('inf'))
    
    def helper(self,root,l,r):
        
        if root==None:
            return True
        
        if root.val>l and root.val<r:
            if (root.left==None or root.left.val<root.val) and \
               (root.right==None or root.right.val>root.val):
                return self.helper(root.left,l,min(root.val,r)) and \
                       self.helper(root.right,max(root.val,l),r)

        return False

方法2，利用中序排序的特点

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

class Solution:
    
    prev=None
    
    def isValidBST(self, root: 'TreeNode') -> 'bool':
        
        if root==None:
            return True
        #判断左边
        if not self.isValidBST(root.left):
            return False
        #判断该节点
        if self.prev!=None and root.val<=self.prev:
            return False
        self.prev=root.val
        #判断右边
        return self.isValidBST(root.right)

---

讨论：

1.一开始我总想用memo记录下面节点的左边最大值和右边最小值，后来发现其实挺难的，看了花花酱的视频恍然大悟，原来可以使用限定范围，感觉简单多了，把代码自己撸出来了（相当于看了hint）

image.png

2.如果中序排列这棵树，那么所有的节点都将是排序的。这个方法非常巧思，要对树的几种排序方法十分熟悉才能做出来！