【LeetCode每天一题】Validate Binary Search Tree(有效的二叉搜

发布时间：2020-12-14 04:31:26 所属栏目：大数据来源：网络整理

导读：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

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:

    2
   /   1   3

Input:?[2,1,3]
Output: true

Example 2:

    5
   /   1   4
?    / ?   3   6

Input: [5,4,null,3,6]
Output: false
Explanation: The root node‘s value is 5 but its right child‘s value is 4.

思路

　　在看到这道题的时候，我想起了二叉搜索树的一个特性就是二叉搜索树的中序遍历是升序排序的。因此根据这个特性。我得出二叉搜索树的中序遍历序列，然后从头到尾进行判断他是否是有序的。如果其中哪一个数字大小关系不满足，则说明不是有效的二叉搜索树。时间复杂度为O(n)，空间复杂度为O(n)。
解决代码

 1 # Definition for a binary tree node.
 2 # class TreeNode(object):
 3 # def __init__(self,x):
 4 # self.val = x
 5 # self.left = None
 6 # self.right = None
 7 
 8 class Solution(object):  9     def isValidBST(self,root): 10         """
11  :type root: TreeNode 12  :rtype: bool 13         """
14         if not root: 15             return True 16         res = [] 17  self.validBFS(root,res) 18         for i in range(1,len(res)): # 从头到尾进行判断是否存在不满足排序的元素。 19             if res[i] <= res[i-1]: 20                 return False 21         return True 22         
23         
24     def validBFS(self,root,res): # 中序遍历函数，将遍历序列添加进去 25         if not root: 26             return
27  self.validBFS(root.left,res) 28  res.append(root.val) 29         self.validBFS(root.right,res)

非递归解决办法

 1 # Definition for a binary tree node.
 2 # class TreeNode(object):
 3 # def __init__(self,root): 10         """
11  :type root: TreeNode 12  :rtype: bool 13         """
14         if not root: 15             return True 16         res,stack = [],[] 17         
18         while stack or root: 19             if root: 20  stack.append(root) 21                 root = root.left 22             else: 23                 root = stack.pop() 24 if res and root.val <= res： # 每次添加前先判断   
return False 26  res.append(root.val) 27                 root = root.right 28         return True

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!