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

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 *	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param root TreeNode类 the root
     * @return bool布尔型vector
     */
    vector<int> InOrderVist(TreeNode* root) {
        TreeNode* curr = root;
        stack<TreeNode*> stk;
        vector<int> result;
        while (curr || !stk.empty()) {
            while (curr) {
                stk.push(curr);
                curr = curr->left;
            }
            curr = stk.top();
            stk.pop();
            result.push_back(curr->val);
            curr = curr->right;
        }
        return result;
    }
    bool IsSearchTree(TreeNode* root) {
        if (!root) {
            return true;
        }

       vector<int> result = InOrderVist(root);
       for (int i = 1; i < result.size(); i++) {
        if (result[i-1] > result[i]) {
            return false;
        }
       }
       return true;
    }
    bool IsCompleteTree(TreeNode* root) {
        if (!root) {
            return true;
        }
        queue<TreeNode*> q;
        q.push(root);
        bool hasNull = false;
        while (!q.empty()) {
            int num = q.size();
            for (int i = 0; i < num; i++) {
                TreeNode* node = q.front();
                q.pop();
                if (hasNull && node) {
                    return false;
                }

                if (node == nullptr) {
                    hasNull = true;
                    continue;
                }
                
                q.push(node->left);
                q.push(node->right);
            }
        }
        return true;
    }
    vector<bool> judgeIt(TreeNode* root) {
        // write code here
        bool isSearchTree = IsSearchTree(root);
        bool isCompleteTree = IsCompleteTree(root);
        return {isSearchTree, isCompleteTree};
    }
};