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

中序遍历+层序遍历

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

class Solution {
public:
    /**
     * 
     * @param root TreeNode类 the root
     * @return bool布尔型vector
     */
    bool isFirst = true;
    bool isSearchTree = true;
    int pre;
    void inOrder(TreeNode* root){
        if(root == NULL) return;
        inOrder(root -> left);
        if(isFirst){
            pre = root -> val;
            isFirst = false;
        }else{
            if(pre >= root -> val){
                isSearchTree = false;
                return;
            }
            pre = root -> val;
        }
        inOrder(root -> right);
    }
    bool isCompTree(TreeNode* root){
        if(root == NULL) return true;
        queue<TreeNode*> q;
        q.push(root);
        int size = 0;
        while(!q.empty()){ //一旦遇到NULL，则后面不能有非空节点
            TreeNode* node = q.front(); q.pop();
            if(node == NULL) break;
            q.push(node -> left);
            q.push(node -> right);
        }
        while(!q.empty() && q.front() == NULL){
            q.pop();
        }
        return q.empty();
    }
    vector<bool> judgeIt(TreeNode* root) {
        // write code here
        inOrder(root);
        return {isSearchTree, isCompTree(root)};
    }
};