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

判断是否为搜索二叉树用中序遍历

判断是否为完全二叉树用层次遍历

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

class Solution {
public:
    /**
     * 
     * @param root TreeNode类 the root
     * @return bool布尔型vector
     */
    bool judge1(TreeNode* root,int &pre){ //判断是否为搜索二叉树
        //中序遍历
        if(root==NULL) return true;
        bool flag1=judge1(root->left,pre);
        bool flag2=root->val>pre;
        pre=root->val;
        bool flag3=judge1(root->right,pre);
        return flag1&&flag2&&flag3;
    }
    bool judge2(TreeNode* root){ //判断是否为完全二叉树
        if(root==NULL) return true;
        queue<TreeNode*> q;
        q.push(root);
        bool flag=false;
        while(!q.empty()){
            TreeNode* node=q.front();
            q.pop();
            if(flag&&(node->left||node->right)){//如果前面有缺少左儿子或者右儿子，但是该节点有儿子，返回false
                return false;
            }
            if(!node->left&&node->right) return false;  //如果二叉树节点有右儿子但是没有左儿子，直接返回false
            if(node->left) q.push(node->left);
            if(node->right) q.push(node->right);
            if(!node->left||!node->right) flag=true;
        }
        return true;
    }
    vector<bool> judgeIt(TreeNode* root) {
        // write code here
        vector<bool> ve(2,false);
        int pre=INT_MIN;
        ve[0]=judge1(root,pre);
        ve[1]=judge2(root);
        return ve;
    }
};