给定一棵二叉树，已知其中的节点没有重复值，请判断该二叉树是否为搜索二叉树和完全二叉树。
输出描述：分别输出是否为搜索二叉树、完全二叉树。
数据范围：二叉树节点数满足 
，二叉树上的值满足 
要求：空间复杂度 )
，时间复杂度
注意：空子树我们认为同时符合搜索二叉树和完全二叉树。
[编程题]判断一棵二叉树是否为搜索二叉树和完全二叉树
class Solution {
public:
vector<bool> judgeIt(TreeNode* root) {
// write code here
vector<bool> res{true,true};
if (!root) return res;
inOrder(root);
for(int i = 1;i<midSeq.size();++i) //检查是否升序序列
if (midSeq[i] < midSeq[i - 1]) {
res[0] = false;
break;
}
res[1] = isComplete(root);
return res;
}
void inOrder(TreeNode* root) { //中序遍历
if (root == nullptr) return;
inOrder(root->left);
midSeq.emplace_back(root->val);
inOrder(root->right);
}
bool isComplete(TreeNode* root) {
queue<TreeNode*> q;
q.push(root);
while (!q.empty()) //层序遍历
{
int len = q.size();
for (int i = 0; i < len; ++i) {
TreeNode* temp = q.front();
if (temp->left && temp->right) { //左右孩子都有
q.push(temp->left);
q.push(temp->right);
q.pop();
}
else if (temp->right) return false; //只有右孩子
else{ //只有左孩子，或者叶子节点
if(temp->left) q.push(temp->left);
q.pop();
while (!q.empty()){ //其后须全是叶子节点
if (q.front()->left || q.front()->right) return false;
q.pop();
}
return true;
}
}
}
}
private:
vector<int> midSeq;//中序遍历序列
};
这是一份可能不是最简洁，但可能最好懂的code。
首先，检查是否搜索二叉树，可以利用中序遍历，这里开辟了额外空间来存储，还额外地多了一次遍历检查是否有序。其实也可以在中序遍历的时候记录每个值，检查是否符合前一个比后一个小，这样时空开销会更小。
其次，完全二叉树的性质是除最后一层之外要求满，最后一层在左。层次遍历的过程中按节点的孩子节点分四种情况，其中左右孩子节点均有是常见的，有右孩子无左孩子违背了性质，有左孩子无右孩子或者达到叶子节点说明其后需全是叶子节点。
以上。
编辑于 2020-09-24 15:04:32
回复(2)
/**
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
class Solution {
public:
/**
*
* @param root TreeNode类 the root
* @return bool布尔型vector
*/
vector<bool> judgeIt(TreeNode* root) {
// write code here
vector<int> v;
vector<bool> ans;
int flag = 0;
inorder(root, v,flag);
ans.push_back(flag==1?false:true);
ans.push_back(isCompleteTree(root));
return ans;
}
//判断二叉搜索树的依据是中序遍历一定是升序序列
void inorder(TreeNode* root,vector<int>& v,int& flag){
if(flag) return;
if(root->left) inorder(root->left, v,flag);
if(!v.empty()&&root->val < v.back()) flag = 1;
v.push_back(root->val);
if(root->right) inorder(root->right, v,flag);
}
//bfs搜索，如果第一次遇到空节点之后又发现非空节点，则非完全二叉树
bool isCompleteTree(TreeNode* root){
if(!root) return true;
queue<TreeNode*> q;
q.push(root);
int flag = 0;
while(!q.empty()){
TreeNode* t = q.front();
q.pop();
if(t->left){
if(flag) return false;
else q.push(t->left);
}
else flag = 1;
if(t->right){
if(flag) return false;
else q.push(t->right);
}
else flag = 1;
}
return true;
}
};
发表于 2021-02-02 16:57:16
回复(2)
public class Solution {
public boolean[] judgeIt (TreeNode root) {
boolean[] res = new boolean[2];
res[0] = true; res[1] = true;
if (root == null) return res;
//res[0] = search(root, Long.MIN_VALUE, Long.MAX_VALUE);
ArrayList<Integer> temp = new ArrayList<>();
inorder(root, temp);
for (int i = 0; i < temp.size() - 1; i++){
if (temp.get(i) > temp.get(i + 1)) res[0] = false;
}
res[1] = all(root);
return res;
}
// 直接DFS返回钟中序遍历，再遍历temp判断
void inorder(TreeNode root, ArrayList<Integer> temp){
if (root == null) return;
inorder(root.left, temp);
temp.add(root.val);
inorder(root.right, temp);
}
//通过边界条件递归判断左右子树是否符合
// boolean search(TreeNode root, long left, long right){
// if (root == null) return true;
// if (root.val > right || root.val < left) return false;
// return search(root.left, left, root.val) && search(root.right, root.val, right);
// }
boolean all(TreeNode root){
if (root == null) return true;
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
boolean flag = false;
while(queue.size() != 0){
TreeNode newroot = queue.poll();
TreeNode left = newroot.left;
TreeNode right = newroot.right;
if ( (left == null && right != null) || // 无左子树有右子树
(flag && !(left == null && right == null)) ) //有残缺且非叶节点
return false;
if (left != null) queue.add(left);
if (right != null) queue.add(right);
// 存在残缺节点
if (left == null || right == null) flag = true;
}
return true;
}
} 两个方法没法揉在一起
发表于 2021-11-18 22:05:29
回复(0)
一次中序遍历同时检查搜索二叉树和完全二叉树
import java.util.*;
/*
* public class TreeNode {
* int val = 0;
* TreeNode left = null;
* TreeNode right = null;
* }
*/
public class Solution {
/**
*
* @param root TreeNode类 the root
* @return bool布尔型一维数组
*/
boolean searchFlag= true;
boolean completeFlag = true;
int num=Integer.MIN_VALUE;
Stack<Integer> stack = new Stack<>();
public boolean[] judgeIt (TreeNode root) {
dfs(root,0);
return new boolean[]{searchFlag, completeFlag};
}
public void dfs(TreeNode root, int len) {
//如果两者为false，则开始剪枝
if(!searchFlag && !completeFlag) return ;
if(root==null){
//判断是否是完全二叉树：
//如果是完全二叉树，那么每个空子叶节点所在路径长度差值不得大于1，并且左子节点路径长度必须大于等于右子节点路径长度
//当节点为空说明是一个空子叶节点，此时将该路径长度与前一个路径（上一个空子节点路径）的长度做比较，如果大于则不是完全二叉树
if(stack.size()>=1 && stack.peek()<len) completeFlag=false;
stack.add(len);
return ;
}
dfs(root.left, len+1);
//判断是否是搜索二叉树：
//如果是搜索二叉树，那么中序遍历的结果应该是递增关系。
//如果此访问节点值小于上一个访问节点值，说明破坏了递增规律，则不是搜索二叉树。
if(root.val>=num){
num = root.val;
}else {
searchFlag=false;
}
dfs(root.right,len+1);
}
}
发表于 2021-07-21 22:04:26
回复(1)
import java.util.*;
//菜鸡解法，蚌埠住了
public class Solution {
public boolean[] judgeIt (TreeNode root) {
boolean ans1 = isSortedTree(root);
boolean ans2 = isWholeTree(root);
return new boolean[]{ans1, ans2};
}
public boolean isSortedTree(TreeNode root) {
if(root==null) return true;
ArrayList<TreeNode> stack = new ArrayList<>();
ArrayList<Integer> list = new ArrayList<>();
while(!stack.isEmpty() || root!=null) {
if(root!=null) {
stack.add(root);
root = root.left;
}
else {
root = stack.remove(stack.size()-1);
list.add(root.val);
root = root.right;
}
}
for(int i=1; i<list.size(); i++) {
if(list.get(i-1)>=list.get(i)) return false;
}
return true;
}
public boolean isWholeTree(TreeNode root) {
if(root==null) return false;
ArrayList<TreeNode> queue = new ArrayList<>();
queue.add(root);
TreeNode head = root;
while(head!=null) {
head = queue.remove(0);
if(head!=null) {
queue.add(head.left);
queue.add(head.right);
}
}
while(!queue.isEmpty()) {
head = queue.remove(0);
if(head!=null) return false;
}
return true;
}
}
发表于 2021-07-15 10:27:26
回复(0)
<Python解法 一次遍历得到结论>
搜索树特性：左子树的最大值小于当前值，右子树的最小值大于当前值。
完全二叉树特性：左右子树至少有一边为满二叉树，且左子树数量大于等于右子树。
满二叉树特性： 节点数目等于2^(depth) -1
由于判断条件过多，如果当前递归已知道不满足条件，就不进行复杂判断和计算。
# class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None # # # @param root TreeNode类 the root # @return bool布尔型一维数组 # tree_flag = True num_flag = True class Solution: def judgeIt(self , root ): # write code here global tree_flag global num_flag self.search_tree(root) return [tree_flag, num_flag] def search_tree(self, root): global tree_flag global num_flag if not tree_flag and not num_flag: return 0, 0, 0, 0 if not root.left and not root.right: return root.val , root.val, 1, 1 result_min = root.val result_max = root.val if root.left: min_left , max_left , num_left, depth_left = self.search_tree(root.left) if max_left > root.val: tree_flag = False if tree_flag: result_min = min(min_left, result_min) result_max = max(max_left, result_max) else: num_left = 0 depth_left = 0 if root.right: min_right , max_right , num_right, depth_right = self.search_tree(root.right) if min_right < root.val: tree_flag = False if tree_flag: result_min = min(min_right, result_min) result_max = max(max_right, result_max) else: num_right = 0 depth_right = 0 if depth_left < depth_right: num_flag = False if num_flag: if num_left != 2**(depth_left) -1: if num_right != 2**(depth_left - 1) - 1: num_flag = False return result_min, result_max, num_left + num_right + 1, max(depth_right, depth_left) + 1
发表于 2021-05-01 19:00:22
回复(0)
class Solution:
def judgeIt(self , root ):
# return [self.isBRT_DFS(root), self.isCBT_DFS(root)]
return [self.isBRT_DFS(root), self.isCBT_BFS(root)]
# 深度优先搜索(DFS)实现 - 判断是否为二叉搜索树
def isBRT_DFS(self, root):
# 空树为二叉搜索树
if not root: return True
# 不满足左孩子节点值<根节点值<右孩子跟节点值, 返回False
if (root.left and root.left.val > root.val) or (root.right and root.right.val < root.val):
return False
# 递归左子树和右子树，同时为二叉搜索树返回True,否则返回False
return self.isBRT_DFS(root.left) and self.isBRT_DFS(root.right)
# 深度优先搜索(DFS)实现 - 判断是否为完全二叉树
def isCBT_DFS(self, root):
# 空树为满二叉树
if not root: return True
# 左子树不为空，右子树为空，继续递归左子树
if root.left and not root.right:
return self.isCBT_DFS(root.left)
# 左子树为空，右子树不为空，不满足满二叉树条件
if not root.left and root.right:
return False
# 递归左子树和右子树，同时为满二叉树则返回True,否则返回False
return self.isCBT_DFS(root.left) and self.isCBT_DFS(root.right)
# 方式二：基于队列的广度优先搜索(BFS)实现 - 判断是否为完全二叉树
# 思路：如果第一次遇到空节点后又遇到非空节点，则为非完全二叉树
def isCBT_BFS(self, root):
if not root: return True
# 用于记录是否遇到空节点
getNoneNode = False
queue = []
queue.append(root)
while queue:
cur = queue.pop()
# 左子树不为空，则将左节点入队列
if cur.left:
queue.insert(0, cur.left)
# 左子树遇到空节点，进行标记
else:
getNoneNode = True
# 右子树不为空
if cur.right:
# 若已经遇到左空节点，返回False，为非满二叉树
if getNoneNode: return False
# 反之，则将右节点入队列
else: queue.insert(0, cur.right)
return True
def judgeIt(self , root ):
# return [self.isBRT_DFS(root), self.isCBT_DFS(root)]
return [self.isBRT_DFS(root), self.isCBT_BFS(root)]
# 深度优先搜索(DFS)实现 - 判断是否为二叉搜索树
def isBRT_DFS(self, root):
# 空树为二叉搜索树
if not root: return True
# 不满足左孩子节点值<根节点值<右孩子跟节点值, 返回False
if (root.left and root.left.val > root.val) or (root.right and root.right.val < root.val):
return False
# 递归左子树和右子树，同时为二叉搜索树返回True,否则返回False
return self.isBRT_DFS(root.left) and self.isBRT_DFS(root.right)
# 深度优先搜索(DFS)实现 - 判断是否为完全二叉树
def isCBT_DFS(self, root):
# 空树为满二叉树
if not root: return True
# 左子树不为空，右子树为空，继续递归左子树
if root.left and not root.right:
return self.isCBT_DFS(root.left)
# 左子树为空，右子树不为空，不满足满二叉树条件
if not root.left and root.right:
return False
# 递归左子树和右子树，同时为满二叉树则返回True,否则返回False
return self.isCBT_DFS(root.left) and self.isCBT_DFS(root.right)
# 方式二：基于队列的广度优先搜索(BFS)实现 - 判断是否为完全二叉树
# 思路：如果第一次遇到空节点后又遇到非空节点，则为非完全二叉树
def isCBT_BFS(self, root):
if not root: return True
# 用于记录是否遇到空节点
getNoneNode = False
queue = []
queue.append(root)
while queue:
cur = queue.pop()
# 左子树不为空，则将左节点入队列
if cur.left:
queue.insert(0, cur.left)
# 左子树遇到空节点，进行标记
else:
getNoneNode = True
# 右子树不为空
if cur.right:
# 若已经遇到左空节点，返回False，为非满二叉树
if getNoneNode: return False
# 反之，则将右节点入队列
else: queue.insert(0, cur.right)
return True
发表于 2021-03-14 20:29:32
回复(0)
递归判断二叉搜索树，层序遍历判断完全二叉树
import java.util.*;
/*
* public class TreeNode {
* int val = 0;
* TreeNode left = null;
* TreeNode right = null;
* }
*/
public class Solution {
/**
*
* @param root TreeNode类 the root
* @return bool布尔型一维数组
*/
public boolean[] judgeIt (TreeNode root) {
// write code here
return new boolean[]{isSearch(root),isComplete(root)};
}
private boolean isSearch(TreeNode root) {
if(root == null) return true;
if(root.left != null && root.left.val > root.val) return false;
if(root.right != null && root.right.val < root.val) return false;
return isSearch(root.left) && isSearch(root.right);
}
private boolean isComplete(TreeNode root){
if(root == null) return true;
LinkedList<TreeNode> queue = new LinkedList<TreeNode>();
queue.add(root);
/*********************************
//SearchByLayer
ArrayList<Character> sbl = new ArrayList<Character>();
while(!queue.isEmpty()) {
TreeNode node = queue.removeFirst();
if(node == null) {
sbl.add('#');
}else {
sbl.add((char)('0'+node.val%10));
queue.add(node.left);
queue.add(node.right);
}
}
int flag = 0;
for(char c : sbl) {
if(c == '#') flag = 1;
if(c <= '9' && c >= '0' && flag == 1) return false;
}
return true;
*********************************/
//将null看作叶子结点可以少写不少代码
while(!queue.isEmpty()) {
TreeNode node = queue.removeFirst();
if(node != null) {
queue.add(node.left);
queue.add(node.right);
}
else {
while(!queue.isEmpty()) {
TreeNode tempNode = queue.removeFirst();
if(tempNode != null) return false;
}
}
}
return true;
}
}
发表于 2021-03-13 09:18:41
回复(0)
/**
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
class Solution {
public:
/**
*
* @param root TreeNode类 the root
* @return bool布尔型vector
*/
vector<bool> judgeIt(TreeNode* root) {
// write code here
if (!root)
return {};
vector<bool> ans(2);
ans[0] = dfs(root);
ans[1] = bfs(root);
return ans;
}
bool dfs(TreeNode *root) {
if (!root)
return true;
if (root->left && root->left->val > root->val)
return false;
if (root->right && root->right->val < root->val)
return false;
return dfs(root->left) && dfs(root->right);
}
bool bfs(TreeNode *root) {
queue<TreeNode*> q;
q.push(root);
//int level = 0;
while (!q.empty()) {
int nums = q.size();
//if (nums != pow(2, level++)) //这个是满二叉树的判断。。
// return false;
for (int i = 0; i < nums; i++) {
TreeNode *tmp = q.front();
q.pop();
if(!tmp->left && tmp->right) //左空有右肯定不是完全二叉树。。
return false;
if (tmp->left)
q.push(tmp->left);
if (tmp->right)
q.push(tmp->right);
}
}
return true;
}
};
编辑于 2021-02-08 12:02:37
回复(0)
import java.util.*;
/*
* public class TreeNode {
* int val = 0;
* TreeNode left = null;
* TreeNode right = null;
* }
*/
import java.util.Queue;
import java.util.LinkedList;
public class Solution {
/**
*
* @param root TreeNode类 the root
* @return bool布尔型一维数组
*/
public boolean[] judgeIt (TreeNode root) {
// write code here
boolean[] check = new boolean[2];
check[0] = isSearch(root, Integer.MIN_VALUE, Integer.MAX_VALUE);
check[1] = isComplete(root);
return check;
}
public boolean isSearch(TreeNode root, int minVal, int maxVal){
if (root == null) return true;
boolean flag = (root.val >= minVal && root.val <= maxVal);
return flag && isSearch(root.left, minVal, root.val) && isSearch(root.right, root.val, maxVal);
}
public boolean isComplete(TreeNode root){
if (root == null) return true;
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
boolean isLeaf = false;
while (!queue.isEmpty()){
int cnt = queue.size();
for(int i = 1;i <= cnt; ++i){
TreeNode now = queue.poll();
if (isLeaf && now.left != null) return false;
if (now.left == null && now.right != null) return false;
if (now.right == null) isLeaf = true;
if (now.left != null) queue.offer(now.left);
if (now.right != null) queue.offer(now.right);
}
}
return true;
}
}
发表于 2021-01-26 10:45:52
回复(0)
1.判断二叉搜索树
仅用左子树举例，注意左子树的所有结点比根小，不仅仅是左值<根值，还有左值大于当前树的最小值。
比如右子树的左子树，它不仅要小于父结点的值，还要大于根节点的值。
2.判断完全二叉树
四种情况递归（麻烦，不如用队列好）
class Solution {
public:
/**
*
* @param root TreeNode类 the root
* @return bool布尔型vector
*/
bool bst(TreeNode* root,int mins,int maxs){
if(root==nullptr) return true;
if(root->val>maxs || root->val<mins) return false;
return bst(root->left,mins,root->val)&&bst(root->right,root->val,maxs);
}
bool flag=true,legel=true;
int level(TreeNode* root){//保证右子树不比左子树低
if(root==nullptr) return 0;
if(root->left==nullptr && root->right!=nullptr) legel=false;
int lefthight=level(root->left);
int righthight=level(root->right);
if(lefthight<righthight) legel=false;
return righthight+1;
}
bool iscom(TreeNode* root){
if(root==nullptr) return true;
if(root->left==nullptr && root->right==nullptr)
flag=false;
else if(root->left!=nullptr && root->right==nullptr){
if(!flag) flag=false;
else return false;
}
else if(root->left==nullptr && root->right!=nullptr)
return false;
return iscom(root->left)&&iscom(root->right);
}
vector<bool> judgeIt(TreeNode* root) {
// write code here
vector<bool> res;
res.push_back(bst(root,INT_MIN,INT_MAX));
level(root);
if(!legel) res.push_back(false);
else res.push_back(iscom(root));
return res;
}
};
编辑于 2021-01-11 19:46:37
回复(2)
1. 利用深度优先搜索+中序遍历判断是不是BST。
2. 利用层序遍历（队列实现）判断是否为完全二叉树。
import java.util.*;
/*
* public class TreeNode {
* int val = 0;
* TreeNode left = null;
* TreeNode right = null;
* }
*/
public class Solution {
/**
*
* @param root TreeNode类 the root
* @return bool布尔型一维数组
*/
public boolean[] judgeIt (TreeNode root) {
// write code here
boolean[] res = {isBST(root), isCBT(root)};
return res;
}
public boolean isBST(TreeNode root) {
long[] prev = {(long)0x80000000 - 1};
return dfs(root, prev);
}
private boolean dfs(TreeNode root, long[] prev){
if(root == null){return true;}
if(!dfs(root.left, prev)){return false;}
if(root.val > prev[0]){
prev[0] = root.val;
}else{
return false;
}
return dfs(root.right, prev);
}
private boolean isCBT(TreeNode root){
if(root == null){return true;}
Deque<TreeNode> queue = new LinkedList<>();
queue.offerLast(root);
boolean reachedNull = false;
while(!queue.isEmpty()){
int len = queue.size();
TreeNode curr;
for(int i = 0; i < len; ++i){
curr = queue.pollFirst();
if(curr.left == null){reachedNull = true;}
else{
if(reachedNull){return false;}
else{queue.offerLast(curr.left);}
}
if(curr.right == null){reachedNull = true;}
else{
if(reachedNull){return false;}
else{queue.offerLast(curr.right);}
}
}
}
return true;
}
}
发表于 2020-11-23 23:34:16
回复(0)
class Solution {
public:
/**
*
* @param root TreeNode类 the root
* @return bool布尔型vector
*/
vector<bool> judgeIt(TreeNode* root) {
vector<bool> res{true,true};
if(root==NULL) return res;
//检测有序
vector<int> nums;
func1(root,nums);
int cur=nums[0];
for(int i=1;i<nums.size();++i){
if(cur>nums[i]){
res[0]=false;
}
}
//检测完全二叉树
vector<TreeNode*> cur_level{root};
res[1]=func2(cur_level);
return res;
}
void func1(TreeNode* root,vector<int>& nums){
if(root==nullptr) return ;
func1(root->left, nums);
nums.push_back(root->val);
func1(root->right,nums);
return ;
}
bool func2(vector<TreeNode*>& cur_level){
int flag=true;
vector<TreeNode*> next_level;
for(int i=0;i<cur_level.size();++i){
if(cur_level[i]!=nullptr){
if(flag==false){//如果前面出现过了空指针
return false;
}
next_level.push_back(cur_level[i]->left);
next_level.push_back(cur_level[i]->right);
}
else{//
flag=false;
}
}
if(next_level.size()==0) return true;
return func2(next_level);
}
}；
现场手撕就卡壳，面完复盘冷静下来就能写出来了，难受啊
发表于 2020-09-08 19:59:28
回复(1)
非递归
/**
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
class Solution {
public:
/**
*
* @param root TreeNode类 the root
* @return bool布尔型vector
*/
bool judgeSearch(TreeNode* root){
if(root==nullptr)
return false;
TreeNode *p = root;
vector<int> tmp;
stack<TreeNode*> s;
while(!s.empty() || p){
while(p){
s.push(p);
p = p->left;
}
if(!s.empty()){
p = s.top();
s.pop();
tmp.push_back(p->val);
p = p->right;
}
}
for(int i = 1; i < tmp.size(); i++)
if(tmp[i] < tmp[i-1])
return false;
return true;
}
bool judgeTotal(TreeNode *root){
if(root==nullptr)
return false;
TreeNode *p = root;
queue<TreeNode*> q;
q.push(root);
while(!q.empty()){
p = q.front();
q.pop();
if(p->left && p->right){
q.push(p->left);
q.push(p->right);
}
else if(p->left==nullptr && p->right)
return false;
else{
if(p->left && p->right==nullptr)
while(!q.empty()){
p = q.front();
q.pop();
if(p->left || p->right)
return false;
}
}
}
return true;
}
vector<bool> judgeIt(TreeNode* root) {
// write code here
vector<bool> res;
res.push_back(judgeSearch(root));
res.push_back(judgeTotal(root));
return res;
}
};
发表于 2020-09-08 10:48:35
回复(3)
# class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None # # # @param root TreeNode类 the root # @return bool布尔型一维数组 # import collections class Solution: def judgeIt(self , root ): # write code here def dfs(root): pre=-1 que=[] while(que&nbs***bsp;root): while(root): que.append(root) root=root.left root=que.pop() if pre>root.val: return False pre=root.val root=root.right return True pre=root.val return dfs(root.right) def isfull(root): que=collections.deque([root]) while(que): c=que.popleft() if not c: while(que): c=que.popleft() if c: return False else: que.append(c.left) que.append(c.right) return True return [dfs(root),isfull(root)] PY的代码，为了减少运行时间，都用的非递归实现，但是还是只能过84.21%，递归的方法只能74%。 我看大家通过的代码都是CPP的。。。 有点无奈
发表于 2020-09-18 14:02:44
回复(0)
import java.util.*;
/*
* public class TreeNode {
* int val = 0;
* TreeNode left = null;
* TreeNode right = null;
* }
*/
public class Solution {
/**
*
* @param root TreeNode类 the root
* @return bool布尔型一维数组
*/
long pre = Long.MIN_VALUE;
public boolean[] judgeIt (TreeNode root) {
// write code here
return new boolean[]{isSBT(root),isCBT(root)};
}
/**
* 判断一棵二叉树是否为搜索二叉树，只要改写一个二叉树中序遍历，在遍历的过程中看节点值是否都是递增的即可。
* @param root
* @return
*/
public boolean isSBT(TreeNode root) {
if (root == null) {
return true;
}
if(!isSBT(root.left)) {
return false;
}
if (root.val <= pre) {
return false;
}
pre = root.val;
return isSBT(root.right);
}
/**
*
* 判断一棵二叉树是否为完全二叉树，依据以下标准会使判断过程变得简单且易实现。
* 1．按层遍历二叉树，从每层的左边向右边依次遍历所有的节点。
* 2．如果当前节点有右孩子节点，但没有左孩子节点，则直接返回 false。
* 3．如果当前节点并不是左右孩子节点全有，那么之后的节点必须都为叶节点，否则返回false。
* 4．遍历过程中如果不返回 false，则遍历结束后返回 true。
* @param root
* @return
*/
public boolean isCBT(TreeNode root) {
if (root == null) {
return true;
}
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
boolean leaf = false;
while (!queue.isEmpty()) {
int size = queue.size();
for (int i = 0; i < size; i++) {
TreeNode node = queue.poll();
//如果当前节点并不是左右孩子节点全有，那么之后的节点必须都为叶节点
if (leaf && (node.left != null || node.right != null)) {
return false;
}
//如果当前节点有右孩子节点，但没有左孩子节点，则直接返回 false
if (node.left == null && node.right != null) {
return false;
}
if (node.left != null) {
queue.offer(node.left);
}
if (node.right != null) {
queue.offer(node.right);
} else {
leaf = true;
}
}
}
return true;
}
}
编辑于 2021-04-06 16:39:51
回复(0)
- 中序遍历ldr不用说，基础。
- bfs：广度优先的while条件一般为（root！=nullptr）而且空节点不写入。现在既写入空节点，又把条件变成遇到一个nullptr就退出。这样如果为非完全二叉树，退出循环时还有数据没有pop干净。最后再遍历queue，还有非空数据说明为非完全二叉树。
class Solution { public: vector<int> ldrVec{INT_MIN};//记录中序遍历 queue<TreeNode*> bfsVec;//queue用来bfs bool A1 = true,A2 = true;//初始化要返回的结果A1，A2 vector<bool> judgeIt(TreeNode* root) { if(root != nullptr){ ldr(root);//ldr bfsVec.push(root);//队列插入root bfs(root);//bfs } return vector<bool>{A1,A2}; } void ldr(TreeNode* root){ if(root != nullptr){ if(root->left!=nullptr)ldr(root->left); if(root->val < ldrVec.back())A1 = false; ldrVec.push_back(root->val); if(root->right!=nullptr)ldr(root->right); } } void bfs(TreeNode* root){ TreeNode* front = nullptr;//队列头指针 while(front = bfsVec.front()){//遇到nullptr结束////如果不是完全二叉树，front会因为 = null而结束，但此时queue并没有pop完全。//即非完全二叉树，queue还有其他元素 bfsVec.push(front->left);//遇到空会写入写入nullptr bfsVec.push(front->right); bfsVec.pop(); } while(!bfsVec.empty()) {//遍历 if (bfsVec.front() != nullptr) { //如果还有其他元素，说明非完全二叉树 A2 = false; } bfsVec.pop(); } } };
发表于 2020-08-23 10:17:58
回复(2)
/**
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
class Solution {
public:
/**
*
* @param root TreeNode类 the root
* @return bool布尔型vector
*/
vector<bool> judgeIt(TreeNode* root) {
// 时间复杂度均为O(N)，空间复杂度均为O(N)
vector<bool> res(2);
res[0] = isBST(root); // 是否二叉搜索树
res[1] = isCBT(root); // 是否完全二叉树
return res;
}
private:
int preVal = INT_MIN; // 上一个节点的值
bool isBST(TreeNode *root) {
if (root == nullptr) return true;
bool left = isBST(root->left);
if (!left || preVal >= root->val) return false;
preVal = root->val;
return isBST(root->right);
}
bool isCBT(TreeNode *root) {
queue<TreeNode*> que;
if (root == nullptr) return true;
que.push(root);
while (!que.empty()) {
int size = que.size();
int flag = 0; // flag为1，表明队列后续的节点必须都是叶子节点
for (int i = 0; i < size; ++i) {
TreeNode *node = que.front();
que.pop();
if (node->left) {
if (flag) return false;
que.push(node->left);
} else flag = 1;
if (node->right) {
if (flag) return false;
else que.push(node->right);
} else flag = 1;
}
}
return true;
}
};
发表于 2022-09-12 18:49:21
回复(0)
/**
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
class Solution {
public:
/**
*
* @param root TreeNode类 the root
* @return bool布尔型vector
*/
vector<int> vec;
void traversal(TreeNode* root){
//中序遍历
if(root==nullptr)return ;
traversal(root->left);
vec.push_back(root->val);
traversal(root->right);
return;
}
bool isComplete(TreeNode* root){
queue<TreeNode*>que;
que.push(root);
//队内必须有元素
while(que.front()){
TreeNode* node=que.front();
que.pop();
que.push(node->left);
que.push(node->right);
}
//队内元素必须全为空
while(que.size()&&!que.front()){
que.pop();
}
return que.empty();
}
vector<bool> judgeIt(TreeNode* root) {
// write code here
vector<bool> res(2,false);
if(root==nullptr){
res[0]=true;
res[1]=true;
return res;
}
traversal(root);
res[0]=true;
for(int i=0;i<vec.size()-1;i++){
if(vec[i]>=vec[i+1]){
res[0]=false;
break;
}
}
res[1]=isComplete(root);
return res;
}
};
发表于 2022-05-18 10:30:55
回复(0)
/**
* #[derive(PartialEq, Eq, Debug, Clone)]
* pub struct TreeNode {
* pub val: i32,
* pub left: Option<Box<TreeNode>>,
* pub right: Option<Box<TreeNode>>,
* }
*
* impl TreeNode {
* #[inline]
* fn new(val: i32) -> Self {
* TreeNode {
* val: val,
* left: None,
* right: None,
* }
* }
* }
*/
struct Solution{
}
impl Solution {
fn new() -> Self {
Solution{}
}
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param root TreeNode类 the root
* @return bool布尔型一维数组
*/
pub fn judgeIt(&self, root: Option<Box<TreeNode>>) -> Vec<bool> {
if root.is_none() {return vec![true, true]}
// write code here
vec![self.isBST(&root).is_some(), self.isCBT(&root)]
}
fn isBST(&self, bt: &Option<Box<TreeNode>>) -> Option<(i32, i32)> {
if bt.is_none() {return None}
let m = self.getVal(&bt);
let mut max = m;
let mut min = m;
if bt.as_ref().unwrap().left.is_some() {
let lmax = self.isBST(&bt.as_ref().unwrap().left);
if lmax.is_none() || lmax.as_ref().unwrap().1 > m {return None}
min = lmax.unwrap().0
}
if bt.as_ref().unwrap().right.is_some() {
let rmin = self.isBST(&bt.as_ref().unwrap().right);
if rmin.is_none() || rmin.as_ref().unwrap().0 < m {return None}
max = rmin.unwrap().1
}
Some((min, max))
}
fn getVal(&self, node: &Option<Box<TreeNode>>) -> i32 {
node.as_ref().unwrap().val
}
fn isCBT(&self, bt: &Option<Box<TreeNode>>) -> bool {
let mut level_node_num = 1; //非最底层节点数满足 2^N
use std::collections::VecDeque;
let mut q = VecDeque::new();
q.push_back(bt);
let mut end = false; //最底下一层结点必须靠左
//层序遍历
while q.len() > 0 {
let _t = q.len();
if _t == level_node_num {
for _ in 0 .. _t {
let node = q.pop_front().unwrap();
if node.as_ref().unwrap().left.is_some() {
if end {return false}
q.push_back(&node.as_ref().unwrap().left);
} else {
end = true;
}
if node.as_ref().unwrap().right.is_some() {
if end {return false}
q.push_back(&node.as_ref().unwrap().right);
} else {
end = true;
}
}
level_node_num *= 2;
} else {
// 最底下一层结点不存在左右孩子
for _ in 0 .. _t {
let node = q.pop_front().unwrap();
if node.as_ref().unwrap().left.is_some() {
return false
}
if node.as_ref().unwrap().right.is_some() {
return false
}
}
}
}
true
}
}
发表于 2024-06-16 22:26:26
回复(0)
问题信息
难度：
117条回答
501收藏
7654浏览
通过挑战的用户
查看代码-
2023-03-04 18:01:03
-
2023-02-26 21:42:50
-
2023-02-16 15:11:17
-
2023-01-12 14:22:56
-
2023-01-02 10:47:47
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
