题意理解

判断该二叉树是否为搜索二叉树和完全二叉树。
搜索二叉树：父结点大于左子树中所有结点，并且小于右子树中所有结点。
完全二叉树：一棵深度为k的有n个结点的二叉树，对树中的结点按从上至下、从左到右的顺序进行编号，如果编号为i（1≤i≤n）的结点与满二叉树中编号为i的结点在二叉树中的位置相同，则这棵二叉树称为完全二叉树。

方法一

二叉搜索树中，每一个结点都大于其左子树中的所有结点，且都小于其右子树中的所有结点。使用中序遍历取出树中所有结点的值val，放入数组中，应该得到一个严格单调递增的数组，即a[i]<a[i+1]。

示意图如下：
图片说明

对于判断是否是完全二叉树，可以考虑进行层次遍历，即当我们在某一行遇到一个空结点时，之后应该不再存在非空结点了。对于宽度优先搜索，自然地想到使用队列存储数据。不断弹出队列头部的结点，将其的孩子结点压入队列（如果该结点是叶子结点，就压入空结点）。

示意图如下：
图片说明
此时将队列头部的null全部弹出，发现队列中还剩下非空结点16，因此该树不是完全二叉树。

具体代码如下：

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

class Solution {
public:
    /**
     * 
     * @param root TreeNode类 the root
     * @return bool布尔型vector
     */
    vector<int> inorderval;
    //中序遍历，把结点值读取出来
    void inorder(TreeNode *root) {
        if (root == nullptr) return;
        inorder(root->left);
        inorderval.push_back(root->val);
        inorder(root->right);
        return;
    }

    bool isSearchTree(TreeNode *root) {
        inorder(root);
        for (int i=0;i<inorderval.size()-1;i++) {//判断数组是否严格单调递增
            if (inorderval[i] >= inorderval[i+1]) return false;
        }
        return true;
    }

    bool isCompletedTree(TreeNode *root) {
        queue<TreeNode*> q;
        q.push(root);
        //弹出队列的头，将其的孩子结点压入队列尾部，直到弹出的是一个空结点。
        while (q.front()) {
            TreeNode *t = q.front();
            q.pop();
            q.push(t->left);
            q.push(t->right);
        }
        //弹出之后的空结点，直到遇到非空结点或者队列为空。
        while (q.size() && !q.front()) {
            q.pop();
        }
        //如果空结点之后又遇到非空结点，说明不是完全二叉树。
        return q.empty();
    }

    vector<bool> judgeIt(TreeNode* root) {
        return {isSearchTree(root),isCompletedTree(root)};
    }
};

时间复杂度： $O(N)$ 。该方法把树遍历了两遍。
空间复杂度： $O(N)$ 。创建了一个数组存储所有的结点值val，同时递归调用栈也消耗了N的空间。

方法二

方法一需要数组来存储树里面的结点，所以可以考虑在遍历的时候直接比较结点的大小关系。注意，父结点不仅仅是要大于其左孩子，而是要大于左子树中所有的结点（或者说左子树中最大的结点）。

给出left和right作为结点比较的上下界，当作递归参数进行传递和更新。初始值为INT_MIN和INT_MAX。更新时，调用左孩子，则下界不变，上界变为父结点的值；调用右孩子，则上界不变，下界为父结点的值。
当结点的值在left和right之间时，表明
（1）该结点与其父结点之间的大小关系正确；
（2）该结点若为左（右）孩子，其不超出下（上）界。
这样可以保证搜索树完全正确。

具体代码如下：

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

class Solution {
public:
    /**
     * 
     * @param root TreeNode类 the root
     * @return bool布尔型vector
     */
    bool isSearchTree(TreeNode *root,int left, int right) {
        if (root == nullptr) return true;
        if (root->val < left || root->val>right) return false;//如果val超出范围，表明不是搜索树
        return isSearchTree(root->left, left, root->val) && isSearchTree(root->right, root->val, right);//进入左子树和右子树
    }

    bool isCompletedTree(TreeNode *root) {
        queue<TreeNode*> q;
        q.push(root);
        //弹出队列的头，将其的孩子结点压入队列尾部，直到弹出的是一个空结点。
        while (q.front()) {
            TreeNode *t = q.front();
            q.pop();
            q.push(t->left);
            q.push(t->right);
        }
        //弹出之后的空结点，直到遇到非空结点或者队列为空。
        while (q.size() && !q.front()) {
            q.pop();
        }
        //如果空结点之后又遇到非空结点，说明不是完全二叉树。
        return q.empty();
    }

    vector<bool> judgeIt(TreeNode* root) {
        return {isSearchTree(root, INT_MIN, INT_MAX),isCompletedTree(root)};
    }
};

时间复杂度： $O(N)$ 。该方法把树遍历了两遍。
空间复杂度： $O(N)$ 。在访问左子树和右子树的时候，递归调用栈消耗了N的空间。

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

题意理解

方法一

方法二