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

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

class Solution {
public:
    /**
     * 
     * @param root TreeNode类 the root
     * @return bool布尔型vector
     */
    vector<int> res; // 将二叉树以中序遍历压入数组res，如果是搜搜二叉树的话，res将以升序排列
    void searchTree(TreeNode* root) {
        if(root==nullptr)
            return;
        searchTree(root->left);
        res.push_back(root->val);
        searchTree(root->right);
    }
    bool fullTree(TreeNode* root) { // 如果二叉树左子树子节点的数量小于右子树，则不是完全二叉树
        if(root == nullptr || (root->left == nullptr && root->right == nullptr))
            return true;
        int left = numTree(root->left);
        int right = numTree(root->right);
        if(left < right)
            return false;
        return fullTree(root->left) && fullTree(root->right);
    }
    int numTree(TreeNode* root) { // 计算每个二叉树子节点的数量
        if(root == nullptr)
            return 0;
        int left = numTree(root->left);
        int right = numTree(root->right);
        return left + right + 1;
    }
    vector<bool> judgeIt(TreeNode* root) {
        // write code here
        vector<bool> ans; // 最后答案
        searchTree(root); // 判断二叉树是不是搜索二叉树
        bool fullT = fullTree(root); // 判断二叉树是不是完全二叉树
        bool searchT = true;
        if(res.size() < 2)
            searchT = true;
        int pre = res[0];
        for(int i = 1; i < res.size(); i++) {
            if(res[i] < pre) {
                searchT = false;
                break;
            }
            pre = res[i];
        }
        ans.push_back(searchT);
        ans.push_back(fullT);
        return ans;
    }

};