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

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 *	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
#include <climits>
class Solution {
public:
    vector<bool> judgeIt(TreeNode* root) {
        if(root == nullptr){
            return {true, true};
        }

        vector<bool> ans={true, true};

        value( root, ans, INT_MIN, INT_MAX );

        ans[1] = wanquan(root);

        return ans;
    }

    bool wanquan(TreeNode* root){
        queue<TreeNode*> q;
        q.push(root);
        
        while( q.front() ){  //层序遍历，遇到实节点，弹出，放入左右节点
            TreeNode* node = q.front();q.pop();

            q.push(node->left);
            q.push(node->right);
        }

        while( q.size() && !q.front() ){  //遇到空节点，再循环，不能出现实节点
           q.pop();
        }

        return q.empty();  //若不为空则表示，后续还有实节点，false
    }

    int value( TreeNode* root, vector<bool>& ans, int up_min, int up_max){
        if(root == nullptr){
            return -1;
        }

        int left = value(root->left, ans, up_min, root->val);

        int right = value(root->right, ans, root->val, up_max);

        if( left != -1 && !(left <= root->val && left >= up_min) ){
            ans[0] = false;
        }

        if( right != -1 && !(right >= root->val && right <= up_max) ){
            ans[0] = false;
        }

        return root->val;   //层数＋1;
    }
};