商城网站规划,东阳网站建设价格,网站自动适应屏幕,微网站用手机可以做吗优质博文#xff1a;IT-BLOG-CN
一、题目
给你一个二叉树的根节点root#xff0c;判断其是否是一个有效的二叉搜索树。有效 二叉搜索树定义如下#xff1a; 【1】节点的左子树只包含 小于 当前节点的数。 【2】节点的右子树只包含 大于 当前节点的数。 【3】所有左子树和右…优质博文IT-BLOG-CN
一、题目
给你一个二叉树的根节点root判断其是否是一个有效的二叉搜索树。有效 二叉搜索树定义如下 【1】节点的左子树只包含 小于 当前节点的数。 【2】节点的右子树只包含 大于 当前节点的数。 【3】所有左子树和右子树自身必须也是二叉搜索树。
示例 1 输入root [2,1,3] 输出true
示例 2 输入root [5,1,4,null,null,3,6] 输出false 解释根节点的值是5但是右子节点的值是4。 树中节点数目范围在[1, 104]内 -231 Node.val 231 - 1 二、代码
【1】递归 要解决这道题首先我们要了解二叉搜索树有什么性质可以给我们利用由题目给出的信息我们可以知道如果该二叉树的左子树不为空则左子树上所有节点的值均小于它的根节点的值 若它的右子树不空则右子树上所有节点的值均大于它的根节点的值它的左右子树也为二叉搜索树。
这启示我们设计一个递归函数helper(root, lower, upper)来递归判断函数表示考虑以root为根的子树判断子树中所有节点的值是否都在(l,r)的范围内注意是开区间。如果root节点的值val不在(l,r)的范围内说明不满足条件直接返回否则我们要继续递归调用检查它的左右子树是否满足如果都满足才说明这是一棵二叉搜索树。
那么根据二叉搜索树的性质在递归调用左子树时我们需要把上界upper改为root.val即调用helper(root.left, lower, root.val)因为左子树里所有节点的值均小于它的根节点的值。同理递归调用右子树时我们需要把下界lower改为root.val即调用helper(root.right, root.val, upper)。
函数递归调用的入口为helper(root, -inf, inf)inf表示一个无穷大的值。
class Solution {public boolean isValidBST(TreeNode root) {return isValidBST(root, Long.MIN_VALUE, Long.MAX_VALUE);}public boolean isValidBST(TreeNode node, long lower, long upper) {if (node null) {return true;}if (node.val lower || node.val upper) {return false;}return isValidBST(node.left, lower, node.val) isValidBST(node.right, node.val, upper);}
}时间复杂度 O(n)其中n为二叉树的节点个数。在递归调用的时候二叉树的每个节点最多被访问一次因此时间复杂度为O(n)。 空间复杂度 O(n)其中n为二叉树的节点个数。递归函数在递归过程中需要为每一层递归函数分配栈空间所以这里需要额外的空间且该空间取决于递归的深度即二叉树的高度。最坏情况下二叉树为一条链树的高度为n递归最深达到n层故最坏情况下空间复杂度为O(n)。
【2】中序遍历 基于方法一中提及的性质我们可以进一步知道二叉搜索树「中序遍历」得到的值构成的序列一定是升序的这启示我们在中序遍历的时候实时检查当前节点的值是否大于前一个中序遍历到的节点的值即可。如果均大于说明这个序列是升序的整棵树是二叉搜索树否则不是下面的代码我们使用栈来模拟中序遍历的过程。
可能有读者不知道中序遍历是什么我们这里简单提及。中序遍历是二叉树的一种遍历方式它先遍历左子树再遍历根节点最后遍历右子树。而我们二叉搜索树保证了左子树的节点的值均小于根节点的值根节点的值均小于右子树的值因此中序遍历以后得到的序列一定是升序序列。
class Solution {public boolean isValidBST(TreeNode root) {DequeTreeNode stack new LinkedListTreeNode();double inorder -Double.MAX_VALUE;while (!stack.isEmpty() || root ! null) {while (root ! null) {stack.push(root);root root.left;}root stack.pop();// 如果中序遍历得到的节点的值小于等于前一个 inorder说明不是二叉搜索树if (root.val inorder) {return false;}inorder root.val;root root.right;}return true;}
}时间复杂度 O(n)其中n为二叉树的节点个数。二叉树的每个节点最多被访问一次因此时间复杂度为O(n)。 空间复杂度 O(n)其中n为二叉树的节点个数。栈最多存储n个节点因此需要额外的O(n)的空间。
