题解 | #判断一棵二叉树是否为搜索二叉树和完全二叉树#

思路：

• 关于搜索二叉树的知识：搜索二叉树左子树上所有值小于根节点，右子树上所有值大于根节点，中序遍历后得到的是一个递增序列。
• 关于完全二叉树的知识：完全二叉树叶节点只能出现在最下层和次下层，并且最下面一层的节点都集中在该层最左边的若干位置的二叉树，出现叶子节点以后的节点都是叶子。 由此，可用二叉树的中序遍历检查是否为一个递增序列判断是否为搜索二叉树，可用二叉树的层次遍历，判断叶子节点之后是否还有非叶子节点。 中序遍历：递归 层次遍历：借助队列

方法一：递归中序+层次遍历

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);
    }
    bool judgeCBT(TreeNode* root){ //判断是否为完全二叉树：层次遍历
        TreeNode* head = root;
        if(head == NULL) 
            return true; //如果是空，则一定是完全二叉树
        queue<TreeNode*> temp; //队列存储，进行层次遍历
        temp.push(head); 
        TreeNode* p;
        bool flag = false; //记录是否开始出现叶子结点
        while(!temp.empty()){
            p = temp.front();
            temp.pop();
            if(p == NULL) {//如果是空，说明其后面都没有孩子了
                flag= true;
                continue;
            }
            if(flag) 
                return false;//如果是true，说明前面出现过叶子结点
            //存入左右孩子作为下一个层次
            temp.push(p->left);
            temp.push(p->right);
        }
        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;
    }
};

复杂度分析：

• 时间复杂度：O(n)，无论中序遍历、层次遍历还是检查排序都是O(n)
• 空间复杂度：O(n)，中序递归最大栈空间和层次队列的最大空间都为O(n)

方法二：非递归中序+层次遍历

class Solution {
public:
    vector<int> sort; //记录二叉树的中序遍历是否有序
    void judgeSBT(TreeNode* root){ //判断是否为搜索二叉树：递归中序遍历
        stack<TreeNode*> s; //设置栈用于遍历
        TreeNode* head = root;
        while (head != NULL || !s.empty()) {
            while (head != NULL) {   //直到没有左节点
                s.push(head);
                head = head->left;
            }
            head = s.top();
            s.pop();
            sort.push_back(head->val);//访问节点
            head = head->right;
        }
    }
    bool judgeCBT(TreeNode* root){ //判断是否为完全二叉树：层次遍历
        TreeNode* head = root;
        if(head == NULL) 
            return true; //如果是空，则一定是完全二叉树
        queue<TreeNode*> temp; //队列存储，进行层次遍历
        temp.push(head); 
        TreeNode* p;
        bool flag = false; //记录是否开始出现叶子结点
        while(!temp.empty()){
            p = temp.front();
            temp.pop();
            if(p == NULL) {//如果是空，说明其后面都没有孩子了
                flag= true;
                continue;
            }
            if(flag) 
                return false;//如果是true，说明前面出现过叶子结点
            //存入左右孩子作为下一个层次
            temp.push(p->left);
            temp.push(p->right);
        }
        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;
    }
};

复杂度分析：

• 时间复杂度：O(n)，无论中序遍历、层次遍历还是检查排序都是O(n)
• 空间复杂度：O(n)，中序递归最大栈空间和层次队列的最大空间都为O(n)