判断一棵二叉树是否为搜索二叉树和完全二叉树（牛客网 / 中序遍历、层次遍历）

题目链接

题目描述

给定一棵二叉树，已经其中没有重复值的节点，请判断该二叉树是否为搜索二叉树和完全二叉树。

输入

{2,1,3}

输出

[true,true]

备注:

n≤500000

思路

判断二叉搜索树：中序遍历，每次比较当前节点p和前一个遍历到的节点pre的值，如果p->val小于pre->val说明中序遍历的序列不符合从小到大排列，不是二叉搜索树。

完全二叉树和满二叉树不同，完全二叉树满足以下条件：

1. 叶子节点都在最后一层或者倒数第二层
2. 叶子节点都向左聚拢

判断完全二叉树：层次遍历，如果某个子节点为空，则标记flag为true，后面如果还有非空的子节点且flag已经为true了，说明必定不是完全二叉树。

完整代码如下：

class Solution {
public:
    TreeNode *pre;
    //判断是否二叉搜索树
    bool ifSearch(TreeNode *p){
        if(!p)
            return true;
        bool ret=ifSearch(p->left);
        if(pre&&p->val<pre->val)
            ret&=false;
        pre=p;
        ret&=ifSearch(p->right);
        return ret;
    }
    //判断是否完全二叉树
    bool ifComplete(TreeNode *p){
        queue<TreeNode*> q;
        q.push(p);
        bool flag=false;
        while(!q.empty()){
            auto t=q.front();
            q.pop();
            if(!t->left)
                flag=true;
            else if(t->left&&flag)
                return false;
            else
                q.push(t->left);
            if(!t->right)
                flag=true;
            else if(t->right&&flag)
                return false;
            else
                q.push(t->right);
        }
        return true;
    }
    vector<bool> judgeIt(TreeNode* root) {
        pre=NULL;
        return vector<bool>{ifSearch(root),ifComplete(root)};
    }
};