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

vlambda
2021-08-15

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

情景提要

牛客题解系列，按照题号顺序开始。

NC60 判断一棵二叉树是否为搜索二叉树

和完全二叉树

题目描述

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

输入输出示例

输入：

{2,1,3}

返回值：

{true,true}

题目分析

思路

判断搜索二叉树：将二叉树按照中序遍历（左中右）,如果有序，那么就是搜索二叉树。code中使用一个全局的pre指针来表示前一个节点，便于与当前节点的值进行比较。

判断完全二叉树：看节点是不是按照层数从上往下，从左往右的填满。这里使用队列，类似模拟层序遍历。将每一层的节点添加到队列中。无论左右节点是否为空，都进行添加。当出现第一个空节点时，依次弹出队列中剩下的所有节点，如果全为空，则说明是完全二叉树，否则就不是。可以在草稿上画完全二叉树和非完全二叉树进行模拟。

代码实现

方法

/** * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * }; */
class Solution {public: /** *  * @param root TreeNode类 the root * @return bool布尔型vector */ //完全二叉树：全部从左向右填满 //搜索二叉树：左小右大的树 TreeNode* pre = nullptr; vector<bool> judgeIt(TreeNode* root) { // write code here //return {judgeSearchTree(root),judgeFullTree(root)}; if(!root) return {true,true}; return {judgeSearchTree(root),judgeFullTree(root)}; } bool judgeSearchTree(TreeNode* root){ bool r = true,l=true; if(root->left) l = judgeSearchTree(root->left); if(pre != nullptr) { if(pre->val > root->val) return false; } pre = root; if(root->right) r = judgeSearchTree(root->right); return l&&r; } // 放到一个队列里面，有nullptr就跳出，看后面有没有非空的 bool judgeFullTree(TreeNode* root){ queue<TreeNode*> q; if(root) q.push(root); TreeNode* node; int i,n; while(!q.empty()){ n=q.size(); for(i=0;i<n;++i){ node = q.front(); q.pop(); if(!node) { while(!q.empty()){ node = q.front(); q.pop(); if(node) return false; } return true; } q.push(node->left); q.push(node->right); } } return true; }};