leetcode 98 验证二叉搜索树

验证二叉搜索树

二叉树的题目好难啊，思路不是很清晰。

首先分析这个题目，BFS树要求右子树的所有节点都大于当前节点值，左子树的所有节点都小于当前节点。

想一下，右子树的最小值，应该是右子树的最最最左侧的一个叶节点，左子树的最大值应该是最最最右侧的叶节点。从下往上似乎不好比较。

如果我们只是考虑每一个小的二叉树。也就是只有三个节点的。什么情况下才是bfs呢？

1. 右子树是bfs
2. 左子树是bfs
3. 当前节点值（大于或小于）对应的值。也就是说，是把当前节点值于上一个节点值做比较。

需要注意的是：

• 初始值的设计，也就是根节点。根节点一定是满足的，只需要

  root.val>float('-inf') and root.val<float('inf')

• 每一次对应的传递值也要注意，
• 对于右节点，需要更改最小值等于父节点的val。保证右节点值大于父节点。
• 对于左节点，需要更改最大值等于父节点的val，保证左节点值小于父节点。

# 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
        """
        # 判断到目前是不是bfs，是就true 不是false
        def dfs(root,maxval, minval):  
            if not root:
                return True
            val = root.val
            if val <= minval or val >= maxval:
                return False
            return dfs(root.left, val, minval) and dfs(root.right, maxval, val)

        return dfs(root,float('inf'),float('-inf'))
           

递归子函数的设计问题，每一次一定要想清楚，函数的设计目的是什么，输入是什么，返回值是什么。