题意

给定一颗指定二叉树，判断其是否为搜索二叉树和完全二叉树

思路

我们可以分别判断二叉树是否为搜索二叉树和完全二叉树。对于搜索二叉树，只需要保证若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值，且其左右子树也为搜索二叉树。因此我们可以直接递归判断二叉树是否为搜索二叉树。

对于完全二叉树，我们按广度优先搜索的顺序搜索，若一个节点没有左节点，那其后搜索到的所有节点都必然为叶子节点，即其左右子树为空，也可以判断某二叉树是否完全二叉树。

代码如下。

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 * };
 */

class Solution {
public:
    /**
     * 
     * @param root TreeNode类 the root
     * @return bool布尔型vector
     */
    bool isBST(TreeNode* root)//搜索二叉树的判断
    {
        if(root == NULL) return true;//空树是搜索二叉树
        if(!isBST(root->left)) return false;
        if(!isBST(root->right)) return false;//若左右子树不为搜索二叉树必然不为搜索二叉树
        TreeNode *now=root->left;
        while(now != NULL && now->right != NULL)
        {
            now=now->right;
        }
        if(now!=NULL && now->val>root->val) return false;//判断左子树一侧是否满足条件
        now=root->right;
        while(now != NULL && now->left != NULL)
        {
            now=now->left;
        }
        if(now!=NULL && now->val<root->val) return false;//判断右子树一侧是否满足条件
        return true;
    }
    bool isCom(TreeNode* root)//完全二叉树的判断
    {
        queue<TreeNode*> k;
        if(root == NULL)
        return true;//空树是完全二叉树
        k.push(root);
        bool flg = true;//是否已经搜索到了一个左子树为空的节点
        while(k.size())
        {
            TreeNode* tmp=k.front();
            if(tmp == NULL) flg=false;
            else
            {
                if(!flg) return false;//不满足完全二叉树的条件
                k.push(tmp->left);
                k.push(tmp->right);//将k的左右子树加入队列
            }
            k.pop();
        }
        return true;
    }
    vector<bool> judgeIt(TreeNode* root) {
        return vector<bool>{isBST(root),isCom(root)};
    }
};

复杂度分析

时间复杂度：$O(n)O(n)$，其中n为二叉树节点数，每个节点都在两次判断过程中被搜索了刚好一次。

空间复杂度：$O(n)O(n)$，为使用的栈空间和队列所占。