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

搜索二叉树的中序遍历是一个递增序列
完全二叉树进行层次遍历时如果碰到了空指针，则队列中后面不能再存在非空元素。有两个含义：

• 左边先满，左边都空了，右边自然不能再存在元素
• 右边都空了，下一层的左边就不能再存在元素，否则高度之差超过了一

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

class Solution {
public:
    /**
     * 
     * @param root TreeNode类 the root
     * @return bool布尔型vector
     */
    vector<int> LNR;
    void inOrder(TreeNode* node){
        if(!node) return;
        inOrder(node->left);
        LNR.push_back(node->val);
        inOrder(node->right);
    }
    bool isFullTree(TreeNode* node){
        if(!node) return true;
        queue<TreeNode*> que;
        que.push(node);
        TreeNode* tmp;
        bool hasChild = true;
        while(que.size()){
            tmp = que.front();
            que.pop();
            if(!tmp) {
                hasChild = false;
                continue;
            }
            if(!hasChild) return false;
            que.push(tmp->left);
            que.push(tmp->right);
        }
        return true;
    } 
    vector<bool> judgeIt(TreeNode* root) {
        // 判断搜索二叉树
        bool isSearchTree = true;
        inOrder(root);
        for(int i = 1; i < LNR.size() && isSearchTree ; ++i){
            if(LNR[i-1]>LNR[i] ) isSearchTree = false;
        }
        return {isSearchTree, isFullTree(root)};
    }
}