解法一：中序遍历（递归）+ 层次遍历

一棵「二叉搜索树」需要满足要求：对于每个结点，左子树上的所有结点小于它，右子树上的所有结点大于它。

判断一棵二叉树是否为「二叉搜索树」的通用方法为：对该二叉树进行中序遍历，若遍历结果为「严格」单调递增的，则是一棵二叉搜索树，否则不是。

这是因为：中序遍历的步骤是：对于每个结点，先访问其「左子树」，再访问该结点，最后访问其「右子树」；而一棵二叉搜索树左子树结点必小于该结点、右子树上的结点必大于该结点，因此中序遍历的结果为严格单调递增。解法一通过「递归」的方式进行中序遍历，并维护了一个数组用以保存中序遍历的结果，遍历数组来判断是否为严格递增的。

判断一棵树是否为「完全二叉树」的方式为：对其进行层次遍历，若遇到一个空结点，则其后面的结点必须全为空结点，否则不是完全二叉树。具体思路如图所示。

图中，黄色结点为空结点，当遍历到「结点6出队列」后，此时队列中的所有元素必须全为空，否则不是一颗完全二叉树。

根据上述思路，实现的代码如下：

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

class Solution {
public:
    /**
     * 
     * @param root TreeNode类 the root
     * @return bool布尔型vector
     */
    vector<bool> judgeIt(TreeNode* root) {
        vector<bool> res(2, false); 
        if (!root) {
            res[0] = false; 
            res[1] = false; 
            return res; 
        }
        vector<int> inorderRes; 
        inorder(root, inorderRes); // 中序遍历
        res[0] = true;
        // 判断中序遍历结果是否升序
        for (int i = 0; i < inorderRes.size() - 1; i ++) {
            if (inorderRes[i] >= inorderRes[i + 1]) {
                res[0] = false;
                break;
            }
        }
          // 层次遍历
        res[1] = levelOrder(root); 
        return res; 
    }

    void inorder(TreeNode* root, vector<int>& inorderRes) {
        if (!root) return; 
        inorder(root->left, inorderRes); // 访问左子树
        inorderRes.push_back(root->val); // 访问根结点
        inorder(root->right, inorderRes); // 访问右子树
        return; 
    }
    bool levelOrder(TreeNode* root) {
        queue<TreeNode*> q; 
        q.push(root); 
        while (q.front()) {
            TreeNode* tmp = q.front(); 
            q.pop(); 
            q.push(tmp->left); 
            q.push(tmp->right); 
        }
        // 队列元素必须全为空
        while (q.size() && !q.front()) {
            q.pop(); 
        }
        return q.empty(); 
    }
};

该方法需要遍历两次树，因此时间复杂度为O(N)；该方法定义了数组和队列分别用来进行中序遍历和层次遍历，因此空间复杂度为O(N)。

解法二：中序遍历（非递归）+ 层次遍历优化

解法二给出了中序遍历的「非递归实现」，其实现思路如图所示。

步骤如下：

1. 定义一个栈s，用来存储待访问的结点；
2. 对每个结点（设为root），若其左孩子不为空，则将其入栈，并将root置于其左孩子的位置；
3. 若其左孩子为空，则访问栈s的栈顶元素（记为t）、并出栈，并将root置为t的右孩子；
4. 重复上述步骤，直至栈s为空且root为空指针。

对于层次遍历，可以优化解法一的两层while循环为一层循环：设标志位flag，若检测到当前结点为空，则置flag为true，若此时后续遇到非空结点，说明不是完全二叉树。

根据上述思路，实现的代码如下：

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

class Solution {
public:
    /**
     * 
     * @param root TreeNode类 the root
     * @return bool布尔型vector
     */
    vector<bool> judgeIt(TreeNode* root) {
        vector<bool> res(2); 
        if (!root) {
            res[0] = false; res[1] = false; 
            return res; 
        }
        // 定义栈 中序遍历
        stack<TreeNode*> s; 
        TreeNode* p = root; 
        int min_ = INT_MIN; 
        res[0] = true;
        while (p || s.size()) {
            while (p) {
                s.push(p); 
                p = p->left; 
            }
            if (s.size()) {
                p = s.top(); 
                // 判断是否严格递增
                if (min_ < p->val) 
                    min_ = p->val; 
                else {
                    res[0] = false;
                    break;
                }
                s.pop(); 
                p = p->right;
            }
        }
        // 定义队列 层次遍历
        queue<TreeNode*> q; 
        bool flag = false; 
        res[1] = true; 
        q.push(root); 
        while (q.size()) {
            TreeNode* tmp = q.front(); 
            q.pop(); 
            // 遇到空结点 flag置为true
            if (!tmp) {
                flag = true; 
                continue; 
            } else {
                // 遇到非空结点
                if (flag) {
                    res[1] = false;
                    break;
                } else { // flag仍为false时，继续遍历
                    q.push(tmp->left); 
                    q.push(tmp->right); 
                }
            }
        }
        return res; 
    }
};

该方法需要遍历两次树，因此时间复杂度为O(N)；该方法定义了栈和队列分别用来进行中序遍历和层次遍历，因此空间复杂度为O(N)。

解法优化：优化中序遍历（递归）

对于解法一中的递归进行中序遍历，可以优化其空间复杂度，即无需定义数组保存结果。注意：此优化方法在递归时需要使用栈空间，空间复杂度为O(N)。

在每次递归时，比较当前元素是否在low到high所定义的范围内；若满足条件则进行下一次递归，否则直接返回false。

实现的代码如下：

    bool inorder(TreeNode* root, int low, int high) {
        if (!root) 
            return true; 
          // 不满足中序遍历递增要求
        if (!(root->val > low && root->val < high)) 
            return false; 
          // 分别递归左子树和右子树，同时更新low和high
        return inorder(root->left, low, root->val) && inorder(root->right, root->val, high); 
    }

在调用该函数时，初始化low和high分别为INT_MIN和INT_MAX。