题目描述
给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。
有效 二叉搜索树定义如下：
- 节点的左
子树
只包含 小于 当前节点的数。 - 节点的右子树只包含 大于 当前节点的数。
- 所有左子树和右子树自身必须也是二叉搜索树。
示例 1：
输入：root = [2,1,3] 输出：true
示例 2：
输入：root = [5,1,4,null,null,3,6] 输出：false 解释：根节点的值是 5 ，但是右子节点的值是 4 。
思路
1）先中序遍历，遍历的数组会是升序
2）检测数组，如果出现不是升序的情况，返回False
# Definition for a binary tree node.
class TreeNode(object):def __init__(self, val=0, left=None, right=None):self.val = valself.left = leftself.right = right
class Solution(object):def traverse(self, root, res):if not root:return []self.traverse(root.left, res)res.append(root.val)self.traverse(root.right, res)def isValidBST(self, root):""":type root: TreeNode:rtype: bool"""if not root:return Trueres = []self.traverse(root, res)for i in range(len(res) - 1):for j in range(i + 1, len(res)):if res[i] >= res[j]:return Falsereturn Trueif __name__ == '__main__':s=Solution()root = TreeNode(2)node1 = TreeNode(1)node2 = TreeNode(3)root.right = node2node1.left = node1node1.left = node1.right = node2.left = node2.right = Noneprint(s.isValidBST(root))
