题解 | #判断一棵二叉树是否为搜索二叉树和完全二叉树# 花儿都谢了

class Solution {
public:
    vector<int> sort; //记录二叉树的中序遍历是否有序
    void judgeSBT(TreeNode* root){ //判断是否为搜索二叉树：递归中序遍历
        TreeNode* head = root;
        if(head == NULL)
            return;
        judgeSBT(head->left);
        sort.push_back(head->val);
        judgeSBT(head->right);
    }
    /*
    使用层次遍历
    1, 如果当前有右节点，但没有左节点，返回false
    2, 如果之前已经出现了没有右节点的节点，后面又出现非叶子节点，返回false
    3, 层次遍历，持续压栈
    */
    bool judgeCBT(TreeNode* root){ //判断是否为完全二叉树：层次遍历
        TreeNode* head = root;
        if(head == NULL) {
            return true; // 空子树为完全二叉树
        }

        queue<TreeNode*> que; //队列存储，进行层次遍历
        que.push(head); 
        TreeNode* p;
        bool hasNoRightLeaf = false; //记录是否开始出现叶子结点
        while(!que.empty()) {
            TreeNode *front = que.front();
            que.pop();
            
//             如果当前有右节点，但没有左节点，返回false
            if (front->right && !front->left) {
                return false;
            }
//             如果之前已经出现了没有右节点的节点，后面又出现非叶子节点，返回false
            if (hasNoRightLeaf && !(!front->left && !front->right)) {
                return false;
            }
            if (front->left) {
                que.push(front->left);
            }
            if (front->right) {
                que.push(front->right);
            } else {
                hasNoRightLeaf = true;
            }
        }
        return true;
    }
    vector<bool> judgeIt(TreeNode* root) {
        vector<bool> res;
        judgeSBT(root);
        bool flag = true;
        for(int i = 1; i < sort.size(); i++){  //检查是否为递增序列
            if(sort[i - 1] > sort[i])
                flag = false;
        }
        res.push_back(flag);
        res.push_back(judgeCBT(root));
        return res;
    }
};