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

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

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

思路如下:判断是否是搜索树使用了递归而不是中序遍历的思路。判断是否是完全二叉树简单的用个层序遍历即可。
    bool IsSearchTree(TreeNode* root,int min,int max)
    {
        if(root==NULL)
            return true;
        if(root->val<min || root->val >max)
            return false;
        //左子树中所有值都要严格小于根节点,因此左子树中所有数能达到的最大值也就
        //必须都要小于根节点了。因此在递归左子树时最小值不变,最大值更新为根节
        //点的值。右子树的递归也是同理。
        return (IsSearchTree(root->left,min,root->val) && IsSearchTree(root->right, root->val, max));
    }
    
    bool IsComplete(TreeNode* root)
    {
        if(root==NULL)
            return true;   
        queue<TreeNode*> BQueue;
        BQueue.push(root);
        while(!BQueue.empty())
        {
            TreeNode* Current=BQueue.front();
            BQueue.pop();
            if(Current->right && (!Current->left))
            {
                return false;
            }
            else if(Current->left && Current->right)
            {
                BQueue.push(Current->left);
                BQueue.push(Current->right);
            }
            else//只有左节点,亦或是左右节点都没有。说明此时只剩下叶子节点了。
            {
                while(!BQueue.empty())
                {
                    Current=BQueue.front();
                    BQueue.pop();
                    if(Current->left || Current->right)
                        return false;
                }
                break;
            }
        }
        return true;
    }
    
    vector<bool> judgeIt(TreeNode* root) {
        // write code here
        vector<bool>result;
        if(root==NULL)
        {
            result.push_back(true);
            result.push_back(true);
            return result;
        }
        result.push_back(IsSearchTree(root,INT_MIN,INT_MAX));
        result.push_back(IsComplete(root));
        return result;
    }


全部评论

相关推荐

我也曾抱有希望:说的好直白
点赞 评论 收藏
分享
1 收藏 评论
分享
牛客网
牛客企业服务