题解 | #判断一棵二叉树是否为搜索二叉树和完全二叉树#(中序遍历和层次遍历)

/**
搜索二叉树 中序遍历 
完全二叉树 层次遍历 
 */
class Solution {
public:
    TreeNode *pre = new TreeNode(-1000000);
    vector<bool> judgeIt(TreeNode* root) {
        bool f1, f2;
        f1 = judgef1(root);
        f2 = judgef2(root);
        return {f1,f2};
    } 
    // 中序遍历有序
    bool judgef1(TreeNode* root){
        if(!root) return true; // 结点为空返回true
        bool left = judgef1(root->left);  // 判断左子树是否有序
        bool cur = pre->val < root->val;  // 判断当前节点是否有序
        pre = root; // 按中序遍历，记录前一个指针
        bool right = judgef1(root->right); // 判断右子树是否有序
        return left&&right&&cur;
    }
    // 层次遍历 当第一次遇到空节点后发现非空节点，则非完全二叉树
    bool judgef2(TreeNode* root){
        if(!root)return true;
        bool f_empty = false; // 第一次碰到空节点，设为true，判断是否遇到非空节点
        queue<TreeNode *> q; 
        q.push(root);
        while(!q.empty()){
            TreeNode * tmp = q.front();
            q.pop();
            if(tmp->left) {
                if(f_empty) return false; // 遇到空节点，还遇到了非空节点返回false
                q.push(tmp->left);
            }
            else f_empty = true; // 标记遇到了非空节点
             if(tmp->right) {
                if(f_empty) return false; // 遇到空节点，还遇到了非空节点返回false
                q.push(tmp->right);
            }
            else f_empty = true; // 标记遇到了非空节点

        }
        return true;
    }
};