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

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

class Solution {
public:
    /**
     * 
     * @param root TreeNode类 the root
     * @return bool布尔型vector
     */
    vector<int> path;
    vector<bool> judgeIt(TreeNode* root) {
        // write code here
        vector<bool> ans;
        dfs(root);
        bool flag = true;
        for(int i = 1; i < path.size();++i){
            if(path[i] < path[i-1]){
                flag = false;break;
            }
        }
        ans.push_back(flag);
        ans.push_back(bfs(root));
        //完全二叉树
        //判断是不是完全二叉树就是用bfs了
        return ans;
    }
    //完全二叉树用的是bfs，把所有的孩子都放上（不论是不是空的孩子）
    //然后，当遇到空孩子的话，就去看看剩下的孩子要是都是空孩子的话，那么就是完全二叉树
    //否则就不是完全二叉树
    bool bfs(TreeNode *root){
        queue<TreeNode *> q;
        q.push(root);
        while(q.front()){
            auto current = q.front();q.pop();
            q.push(current->left);
            q.push(current->right);
        }
        while(q.size() && !q.front()){
            q.pop();
        }
        return q.empty();
    }
    //二叉搜索树的中序遍历就是升序的
    void dfs(TreeNode *root){
        if(root == nullptr)return;
        dfs(root->left);
        path.push_back(root->val);
        dfs(root->right);
    }
};