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

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

class Solution {
public:
    /**
     * 
     * @param root TreeNode类 the root
     * @return bool布尔型vector
     */
    vector<bool> judgeIt(TreeNode* root) {
        // write code here
        vector<bool> res(2,false);
        res[0]=isBST(root);
        res[1]=isCBT(root);
        return res;
    }
    //判断是否是二叉搜索树，采用中序遍历，如果出现当前遍历的节点值小于上一个保存的val，那么就返回失败。
    bool isBST(TreeNode* root)
    {
        int lastval = INT_MIN;
        stack<TreeNode*> st;
        while(st.size()||root!=nullptr)
        {
            while(root!=nullptr)
            {
                st.push(root);
                root=root->left;
            }
            if(st.size())
            {
                root=st.top();
                st.pop();
                if(root->val < lastval)
                    return false;
                lastval=root->val;
                root=root->right;
            }
        }
        return true;
    }
    //层次遍历，在遍历的过程中如果遇到了空指针，说明某个节点的孩子节点开始为空
    //那么在其后面的所有节点的孩子节点都应该为空，如果不满足返回false
    bool isCBT(TreeNode* root)
    {
        deque<TreeNode*> deq;
        deq.push_back(root);
        while(deq.size())
        {
            root=deq.front();
            deq.pop_front();
            if(root==nullptr)
                break;
            deq.push_back(root->left);
            deq.push_back(root->right);
        }
        while(deq.size()){
            root=deq.front();
            deq.pop_front();
            if(root!=nullptr)
                return false;
        }  
        return true;
    }
};