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

判断一棵二叉树是否为搜索二叉树和完全二叉树

http://www.nowcoder.com/practice/f31fc6d3caf24e7f8b4deb5cd9b5fa97

 * 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,其他情况也需要全覆盖。
全部评论

相关推荐

宇算唯航:目测实缴资本不超100W的小公司
点赞 评论 收藏
分享
头顶尖尖的程序员:我是26届的不太懂,25届不应该是找的正式工作吗?为什么还在找实习?大四还实习的话是为了能转正的的岗位吗
点赞 评论 收藏
分享
自学java狠狠赚一...:骗你点star的,港卵公司,记得把star收回去
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
07-07 13:47
机械打工仔:你自己匿名可以,这么好的公司就别给它匿名了
点赞 评论 收藏
分享
评论
1
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务