没想出来,郁闷。看了大佬的题解才解出来的。
相对来说第一个是比较简单的搜索二叉树。一个dfs无脑搞定。
第二个完全二叉树判断难点在于层次遍历这个知识点。之前搞过,但是忘了。多总结,回顾。谨记。
vector<bool> judgeIt(TreeNode* root) {
bool isSearch = judgeTreeSearch(root,INT32_MIN,INT32_MAX);
bool isComplete = judgeTreeComplete(root);
// write code here
return {isSearch,isComplete};
}
bool judgeTreeSearch(TreeNode* root,int left,int right) {
if(root == NULL){
return true;
}
if(root->val <= left || root->val >= right)return false;
return judgeTreeSearch(root->left,left,root->val) && judgeTreeSearch(root->right,root->val,right);
}
bool judgeTreeComplete(TreeNode* root) {
if(root == NULL) return true;
queue<TreeNode *> queue;
queue.push(root);
bool flag = false; //标记之前是否出现过空节点
while(!queue.empty()){
root = queue.front();
queue.pop();
if(root == NULL){
flag = true;
continue;
}
//层次顺序遍历,之前就存在空节点,因为左对齐,那么后面都不应该有非空节点存在。
if(flag){
return false;
}
queue.push(root->left);
queue.push(root->right);
}
return true;
}



京公网安备 11010502036488号