判断一棵二叉树是否为搜索二叉树和完全二叉树

[编程题]判断一棵二叉树是否为搜索二叉树和完全二叉树

热度指数：53064 时间限制：C/C++ 5秒，其他语言10秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定一棵二叉树，已知其中的节点没有重复值，请判断该二叉树是否为搜索二叉树和完全二叉树。

输出描述：分别输出是否为搜索二叉树、完全二叉树。

数据范围：二叉树节点数满足 $0 \le n \le 500000$ ，二叉树上的值满足 $0 \le val \le 100000$

要求：空间复杂度 $O(n)$ ，时间复杂度 $O(n)$

注意：空子树我们认为同时符合搜索二叉树和完全二叉树。

示例1

输入

{2,1,3}

输出

[true,true]

示例2

输入

{1,#,2}

输出

[true,false]

说明

由于节点的右儿子大于根节点，无左子树，所以是搜索二叉树但不是完全二叉树

示例3

输入

{}

输出

[true,true]

说明：本题目包含复杂数据结构TreeNode，点此查看相关信息

算法知识视频讲解

ajaj

发表于 2021-07-18 19:18:27

精华题解思路: 从题中给出的有效信息：二叉树是否为搜索二叉树和完全二叉树故此二叉树搜索树采用递归的方式解决，完全二叉树使用bfs对其进行求解方法一：递归+广度优先遍历具体做法：搜索树：使用递归的方式进行求解，判断该二叉树的左子树不为空，则左子树上所有节点的值均小于的根节点的值；若它的右子树展开全文

牛客786963925号

发表于 2021-07-12 18:06:59

精华题解解法一：中序遍历（递归）+ 层次遍历一棵「二叉搜索树」需要满足要求：对于每个结点，左子树上的所有结点小于它，右子树上的所有结点大于它。判断一棵二叉树是否为「二叉搜索树」的通用方法为：对该二叉树进行中序遍历，若遍历结果为「严格」单调递增的，则是一棵二叉搜索树，否则不是。这是因为：中序遍历的步骤是展开全文

下一次什么时候可以修改昵称

发表于 2020-11-01 14:45:28

LeetCode98. 验证二叉搜索树算法 1.递归 2.重载一个函数，界定节点值的范围(lower, upper) 3.递归判断左子树和右子树是否是二叉搜索树 public boolean isValidBST(TreeNode root) { return isValidBST 展开全文

laugh_often

发表于 2021-02-26 11:50:37

/** * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; 展开全文

摸鱼学大师

发表于 2021-07-14 20:04:13

思路：关于搜索二叉树的知识：搜索二叉树左子树上所有值小于根节点，右子树上所有值大于根节点，中序遍历后得到的是一个递增序列。关于完全二叉树的知识：完全二叉树叶节点只能出现在最下层和次下层，并且最下面一层的节点都集中在该层最左边的若干位置的二叉树，出现叶子节点以后的节点都是叶子。由此，可用二叉树展开全文