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

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

#include <vector>
class Solution {
public:
    /**
     * 
     * @param root TreeNode类 the root
     * @return bool布尔型vector
     */
    bool absoluteTree(TreeNode* u)
    {
        if(!u) return true;
        queue<TreeNode*> q;
        vector<TreeNode*> v;
        q.push(u), v.push_back(u);
        while(!q.empty())
        {
            auto x=q.front();
            q.pop();
            if(x->left) q.push(x->left), v.push_back(x->left);
            if(x->right) q.push(x->right), v.push_back(x->right);
        }
        int i=0;
        while(i<v.size() && v[i]->left && v[i]->right) i++; //前面的都是有左右子树的节点
        if(i>=v.size()) return true;  //若这里已经遍历完了说明是满二叉树
        if(v[i]->right) return false; // 中间那个节点不能只有右子树
        for(i=i+1;i<v.size();i++)  // 执行到这里说明后面的都必须是叶子节点
            if(v[i]->left || v[i]->right) return false;
        return true;
    }

    bool searchTree(TreeNode* u, int l, int r)
    {
        if(!u) return true;
        if(u->val <= l || u->val >=r) return false;
        return searchTree(u->left, l, u->val) && searchTree(u->right, u->val, r);
    }

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

### 思路

1. 判断搜索二叉树，递归判断即可。dfs(u,l,r)，u表示子树的根节点，l和r分别为该子树的范围（根节点的范围）

* 判断根节点是否在反问内，若不在直接返回false

* 判断左右子树是否在范围内（若存在）：左子树：dfs(u->left, l, u->val) ; 右子树：dfs(u->right, u->val, r)

    bool searchTree(TreeNode* u, int l, int r)
    {
        if(!u) return true;
        if(u->val <= l || u->val >=r) return false;
        return searchTree(u->left, l, u->val) && searchTree(u->right, u->val, r);
    }

1. 判断完全二叉树。我们可以发现在完全二叉树的层序遍历中，前面的节点都有左右子树，中间可能存在一个只有一个子树的节点（只能是左子树），之后全是叶子节点。
2. 因此可以将二叉树的层序遍历存储在vector中，然后检查vector中的元素是否满足上述条件。注意层序遍历需要一个queue，若想节省空间也可以用vector模拟队列