NC60. 判断一棵二叉树是否为搜索二叉树和完全二叉树
描述
示例1
输入:
{2,1,3}
输出:
[true,true]
示例2
输入:
{1,#,2}
输出:
[true,false]
说明:
由于节点的右儿子大于根节点，无左子树，所以是搜索二叉树但不是完全二叉树示例3
输入:
{}
输出:
[true,true]
C++ 解法, 执行用时: 21ms, 内存消耗: 7360KB, 提交时间: 2021-06-22
static const auto io_sync_off = []()
{
// turn off sync
std::ios::sync_with_stdio(false);
// untie in/out streams
std::cin.tie(nullptr);
return nullptr;
}();
/**
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
class Solution {
public:
TreeNode *pLast;
/**
*
* @param root TreeNode类 the root
* @return bool布尔型vector
*/
vector<bool> judgeIt(TreeNode* root) {
// write code here
if( !root ) return {true, true};
pLast = nullptr;
vector<bool> res{my_mid_ergodic(root), true};
queue<TreeNode *> pTN_queue{ {root} }; TreeNode *pTN;
while(pTN = pTN_queue.front())
{
pTN_queue.pop();
pTN_queue.push( pTN->left );
pTN_queue.push( pTN->right );
}
pTN_queue.pop();
while( !pTN_queue.empty() )
{
if( pTN_queue.front() ){ res[1] = false; break; }
pTN_queue.pop();
}
return res;
}
bool my_mid_ergodic(TreeNode *root)
{
if(root){
if(root->left && !my_mid_ergodic( root->left )) return false;
if(pLast && pLast->val >=root->val) return false;
pLast = root;
if(root->right && !my_mid_ergodic( root->right )) return false;
}
return true;
}
};
C++ 解法, 执行用时: 21ms, 内存消耗: 7424KB, 提交时间: 2021-09-27
static const auto io_sync_off = []()
{
// turn off sync
std::ios::sync_with_stdio(false);
// untie in/out streams
std::cin.tie(nullptr);
return nullptr;
}();
/**
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
class Solution {
public:
TreeNode *pLast;
/**
*
* @param root TreeNode类 the root
* @return bool布尔型vector
*/
vector<bool> judgeIt(TreeNode* root) {
// write code here
// if( !root ) return {true, true};
pLast = nullptr;
vector<bool> res{my_mid_ergodic(root), true};
queue<TreeNode *> pTN_queue{ {root} }; TreeNode *pTN;
while(pTN = pTN_queue.front())
{
pTN_queue.pop();
pTN_queue.push( pTN->left );
pTN_queue.push( pTN->right );
}
pTN_queue.pop();
while( !pTN_queue.empty() )
{
if( pTN_queue.front() ){ res[1] = false; break; }
pTN_queue.pop();
}
return res;
}
bool my_mid_ergodic(TreeNode *root)
{
if(root){
if(root->left && !my_mid_ergodic( root->left )) return false;
if(pLast && pLast->val >=root->val) return false;
pLast = root;
if(root->right && !my_mid_ergodic( root->right )) return false;
}
return true;
}
};
C++ 解法, 执行用时: 21ms, 内存消耗: 7588KB, 提交时间: 2021-08-23
/**
* 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) {
return vector<bool>({dfs(root), bfs(root)});
}
bool dfs(TreeNode* root, int n_min = INT_MIN, int n_max = INT_MAX) {
if (root == nullptr) {
return true;
}
if (root -> val < n_min || root -> val > n_max) {
return false;
}
if ((root -> val == INT_MIN && root -> left) || (root -> val == INT_MAX && root -> right)) {
return false;
}
return dfs(root -> left, n_min, root -> val - 1) && dfs(root -> right, root -> val + 1, n_max);
}
bool bfs(TreeNode* root) {
if (root == nullptr) {
return true;
}
queue<TreeNode*> q;
q.push(root);
int n, if_end = 0;
while (!q.empty()) {
n = q.size();
while (n --) {
auto t = q.front();
q.pop();
if (if_end && (t -> left || t -> right)) {
return false;
}
if (t -> left) {
q.push(t -> left);
if (t -> right) {
q.push(t -> right);
} else {
if_end = 1;
}
} else {
if (t -> right) {
return false;
} else {
if_end = 1;
}
}
}
}
return true;
}
};
int x = []() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
return 0;
}();
C++ 解法, 执行用时: 21ms, 内存消耗: 8200KB, 提交时间: 2021-07-31
static const auto io_sync_off = []()
{
// turn off sync
std::ios::sync_with_stdio(false);
// untie in/out streams
std::cin.tie(nullptr);
return nullptr;
}();
/**
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
class Solution {
public:
TreeNode *pLast;
/**
*
* @param root TreeNode类 the root
* @return bool布尔型vector
*/
vector<bool> judgeIt(TreeNode* root) {
// write code here
if( !root ) return {true, true};
pLast = nullptr;
vector<bool> res{my_mid_ergodic(root), true};
//2.树不为空
queue<TreeNode*> q;
q.push(root);
while (!q.empty())
{
TreeNode *top = q.front();
//2.1如果该节点两个孩子都有，则直接pop
if (top->left && top->right)
{
q.pop();
q.push(top->left);
q.push(top->right);
}
//2.2如果该节点左孩子为空，右孩子不为空，则一定不是完全二叉树
if (top->left == NULL && top->right)
{
res[1] = false;
break;
}
//2.3如果该节点左孩子不为空，右孩子为空或者该节点为叶子节点，则该节点之后的所有结点都是叶子节点
if ((top->left && top->right == NULL) || (top->left == NULL && top->right == NULL))
{
if (NULL != top->left && NULL == top->right)
{
q.push(top->left);
}
q.pop(); //则该节点之后的所有结点都是叶子节点
while (!q.empty())
{
top = q.front();
if (top->left == NULL && top->right == NULL)
{
q.pop();
}
else
{
res[1] = false;
return res;
}
}
}
}
/*queue<TreeNode *> pTN_queue{ {root} }; TreeNode *pTN;
while(pTN = pTN_queue.front())
{
pTN_queue.pop();
pTN_queue.push( pTN->left );
pTN_queue.push( pTN->right );
}
pTN_queue.pop();
while( !pTN_queue.empty() )
{
if( pTN_queue.front() ){ res[1] = false; break; }
pTN_queue.pop();
}*/
return res;
}
bool my_mid_ergodic(TreeNode *root)
{
if(root){
if(root->left && !my_mid_ergodic( root->left )) return false;
if(pLast && pLast->val >=root->val) return false;
pLast = root;
if(root->right && !my_mid_ergodic( root->right )) return false;
}
return true;
}
};
C++ 解法, 执行用时: 22ms, 内存消耗: 8292KB, 提交时间: 2021-07-29
// /**
// * struct TreeNode {
// * int val;
// * struct TreeNode *left;
// * struct TreeNode *right;
// * };
// */
// class Solution {
// public:
// /**
// *
// * @param root TreeNode类 the root
// * @return bool布尔型vector
// */
// TreeNode* tmp;
// vector<bool> judgeIt(TreeNode* root) {
// // write code here
// if (root==nullptr) return {true, true};
// queue<TreeNode*> Q;
// Q.push(root);
// bool isAllTree = true;
// TreeNode* node = Q.front();
// while (node) {
// Q.pop();
// Q.push(node->left);
// Q.push(node->right);
// }
// Q.pop();
// while (!Q.empty()) {
// if (Q.front()) {
// isAllTree = false;
// break;
// }
// Q.pop();
// }
// return {isSearchTree(root), isAllTree};
// }
// bool isSearchTree(TreeNode* root) {
// if (root) {
// if (root->left&&!isSearchTree(root->left))
// return false;
// if (tmp&&tmp->val>=root->val)
// return false;
// tmp = root;
// if (root->right&&!isSearchTree(root->right))
// return false;
// }
// return true;
// }
// };
static const auto io_sync_off = []()
{
// turn off sync
std::ios::sync_with_stdio(false);
// untie in/out streams
std::cin.tie(nullptr);
return nullptr;
}();
/**
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
class Solution {
public:
TreeNode *pLast;
/**
*
* @param root TreeNode类 the root
* @return bool布尔型vector
*/
vector<bool> judgeIt(TreeNode* root) {
// write code here
if( !root ) return {true, true};
pLast = nullptr;
vector<bool> res{my_mid_ergodic(root), true};
queue<TreeNode *> pTN_queue{ {root} }; TreeNode *pTN;
while(pTN = pTN_queue.front())
{
pTN_queue.pop();
pTN_queue.push( pTN->left );
pTN_queue.push( pTN->right );
}
pTN_queue.pop();
while( !pTN_queue.empty() )
{
if( pTN_queue.front() ){ res[1] = false; break; }
pTN_queue.pop();
}
return res;
}
bool my_mid_ergodic(TreeNode *root)
{
if(root){
if(root->left && !my_mid_ergodic( root->left )) return false;
if(pLast && pLast->val >=root->val) return false;
pLast = root;
if(root->right && !my_mid_ergodic( root->right )) return false;
}
return true;
}
};