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

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

class Solution {
public:
    /**
     * 
     * @param root TreeNode类 the root
     * @return bool布尔型vector
     */
    bool isBST(TreeNode* root) {
        function<bool(TreeNode*, int, int)> helper = [&](TreeNode* root, int mn, int mx) {
            if (root == nullptr) return true;
            if (root->val < mn or root->val > mx) return false;
            return helper(root->left, mn, root->val) and helper(root->right, root->val, mx);
        };
        return helper(root, INT_MIN, INT_MAX);
    }
    bool isComplete(TreeNode* root) {
        if (root == nullptr) return true;
        queue<TreeNode*> q;
        q.push(root);
        int level = 1;
        while (!q.empty()) {
            int size = q.size();
            bool flag = false;
            for (int i = 0; i < size; i++) {
                TreeNode* temp = q.front();
                q.pop();
                if (temp->left) {
                    if (flag) return false;
                    q.push(temp->left);
                } else {
                    flag = true;
                } 
                if (temp->right) {
                    if (flag) return false;
                    q.push(temp->right);
                } else {
                    flag = true;
                }
            }
            if (!q.empty() and size != pow(2, level - 1)) return false;
            level++;
        }
        return true;
    }
    vector<bool> judgeIt(TreeNode* root) {
        // write code here
        vector<bool> ans;
        if (isBST(root)) ans.push_back(true);
        else ans.push_back(false);
        if (isComplete(root)) ans.push_back(true);
        else ans.push_back(false);
        return ans;
    }
};