看到二叉搜索树就思考中序遍历，如果是二叉搜索树则中序遍历结果数组应该为升序数组。对完全二叉树使用层序遍历，对于空节点则用一个-1来占位。最后判断层序遍历结果-1后面是否存在有效数字，如果存在则不是完全二叉树。二叉搜索树遍历和判断是否升序时间复杂度为O(n)，层序遍历和判断是否有序时间复杂度为O(n),所以总时间复杂度为O(n),空间复杂度为O(n)。
class Solution {
  public:
    /**
     *
     * @param root TreeNode类 the root
     * @return bool布尔型vector
     */
    vector<int> res;
    vector<int> res1;
    vector<bool> judgeIt(TreeNode* root) {
        // write code here
        vector<bool> out;
        if (root == NULL) {
            out.push_back(true);
            out.push_back(true);
            return out;
        }
        bool resbs = true, resfull = true;
        dfs_bs(root);
        bfs_full(root);
        for (int i = 1; i < res.size(); i++) {
            if (res[i] < res[i - 1]) {
                resbs = false;
                break;
            }
        }
        for (int i = 0; i < res1.size(); i++) {
            cout << res1[i] << endl;
            if (res1[i] == -1) {
                while (i < res1.size()) {
                    if (res1[i] != -1) {
                        resfull = false;
                        break;
                    }
                    i++;
                }
            }
        }
        out.push_back(resbs);
        out.push_back(resfull);
        return out;
    }
    void dfs_bs(TreeNode* root) {
        if (root == NULL)return;
        dfs_bs(root->left);
        res.push_back(root->val);
        dfs_bs(root->right);
    }
    void bfs_full(TreeNode* root) {
        if (root == NULL)return;
        queue<TreeNode*> q;
        q.push(root);
        TreeNode* emp = new TreeNode(-1);
        while (!q.empty()) {
            TreeNode* tmp = q.front();
            q.pop();
            if (tmp == emp) {
                res1.push_back(-1);
            } else {
                res1.push_back(tmp->val);
                if (tmp->left != NULL) {
                    q.push(tmp->left);
                } else {
                    q.push(emp);
                }
                if (tmp->right != NULL) {
                    q.push(tmp->right);
                } else {
                    q.push(emp);
                }
            }
        }
    }
};