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

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

#include <queue>
class Solution {
public:
    /**
     * 
     * @param root TreeNode类 the root
     * @return bool布尔型vector
     */
    bool judgeSearch(TreeNode *root, int l, int r) {
        if (!root) {
            return true;
        }
        return root->val > l && root->val < r && judgeSearch(root->left, l, root->val) && judgeSearch(root->right, root->val, r);
    }

    bool judgeComplete(TreeNode *root) {
        if (!root) {
            return true;
        }
        queue<TreeNode *> q;
        q.push(root);
        while (!q.empty()) {
            auto now = q.front();
            q.pop();
            if (now->left && now->right) {
                q.push(now->left);
                q.push(now->right);
            } else if (now->right) {
                return false;
            } else {
                if (now->left) {
                    q.push(now->left);
                }
                while (!q.empty()) {
                    if (q.front()->left || q.front()->right) {
                        return false;
                    }
                    q.pop();
                }
                return true;
            }
        }
        return true;
    }

    vector<bool> judgeIt(TreeNode* root) {
        return {judgeSearch(root, INT_MIN, INT_MAX), judgeComplete(root)};
    }
};

思路：

* 判断搜索二叉树：递归。要注意，虽然数据范围给的是0~100000，但是把上下界设置为-1、100001实际上会出错……

* 判断完全二叉树：层序遍历。遍历到第一次出现子节点为空，将队列中剩余的节点全部pop出来，它们的子节点必须都为空。