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

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

class Solution {
public:
    /**
     * 
     * @param root TreeNode类 the root
     * @return bool布尔型vector
     */
    bool search_jug=true;
    bool total_jug=true;
    bool over=true;
    int tall=0;
    vector<bool> judgeIt(TreeNode* root) {
        // write code here
        vector<bool> ans;
        TreeNode *node=root;
        if(root==NULL){
            ans.push_back(true);
            ans.push_back(true);
            return ans;
        }
        while(node->left!=NULL){
            node=node->left;
            tall=tall+1;
        }
        cout<<tall;
        jugtree(root,0,INT_MAX,INT_MIN);
        ans.push_back(search_jug);
        ans.push_back(total_jug);
        return ans;
    }
    void jugtree(TreeNode* node,int height,int max,int min){
        if(node->val>=max||node->val<=min) search_jug=false;
        if(height>tall) total_jug=false;
        if(!(total_jug||search_jug)) return;
        if(node->left!=NULL&&node->right!=NULL){
            if(height==tall-1&&!over) total_jug=false;
            jugtree(node->left,height+1,node->val,min);
            jugtree(node->right,height+1,max,node->val);
        }
        else{
            if(height==tall-1){
                if(node->left==NULL&&node->right==NULL){
                    over=false;
                }
                else{
                    if(node->left!=NULL){
                        jugtree(node->left,height+1,node->val,min);
                        if(over) over=false;
                        else total_jug=false;
                    }
                    else{
                        jugtree(node->right,height+1,max,node->val);
                        total_jug=false;
                    }
                }
              }
            else{
                if(node->left==NULL&&node->right==NULL) return;
                total_jug=false;
                if(node->left!=NULL) jugtree(node->left,height+1,node->val,min);
                else jugtree(node->right,height+1,max,node->val);
            }
        }
    }
};
```jinxing
做出来了，记录一下，采用的就是深度遍历二叉树，对于完全二叉树和搜索二叉树分别进行不同的判断策略，搜索二叉树就是在遍历中对于子树设立一个max、min，即结点应该在的范围，并根据搜索二叉树的性质修改，若不满足则将search_jug改为false，而完全二叉树则首先while循环最左子树确定深度h，然后后续利用深度进行系列判断，关键是在当前深度为n-1时，若有一个节点不满足同时有左右结点，则记over为false，若只有右节点则直接total_jug为false，但若这个节点仍保持完全二叉树，若同高度下一节点又遇到over要改变，而此时over已经改为false，则直接改变total_jug，其他情况也需要全覆盖。