专栏首页Bingo的深度学习杂货店判断一棵满二叉树是否为二叉搜索树

判断一棵满二叉树是否为二叉搜索树

题目描述:

给定一棵满二叉树,判定该树是否为二叉搜索树,是的话打印 True,不是的话打印 False。

说明:

  • a. 二叉搜索树(Binary Search Tree),它或者是一棵空树,或者是具有下列性质的二叉树: 若它的左子树不空,则左子树上所有结点的值均小于它的根结点的值; 若它的右子树不空,则右子树上所有结点的值均大于它的根结点的值; 它的左、右子树也分别为二叉搜索树。
  • b. 满二叉树,除最后一层无任何子节点外,每一层上的所有结点都有两个子结点二叉树
  • c. 树内节点数不超过 10000,非空节点值为大于 0 小于 65536 的整数,空树或空节点输入为 None
输入描述:

从根节点开始,逐层输入每个节点的值,空树或空节点输入为 None 比如:10,5,15,3,7,13,18

输出描述:

是二叉搜索树的话打印 True,不是的话打印 False

示例1

输入 10,5,15,3,7,13,18 输出 True

解题思路:

1、先处理输入数据,将输入保存在列表 list 中,注意要将字符数字转化为整数数字, 'None' 转化为 None; 2、定义树结构,根据 list 递归构造这棵满二叉树; 3、判断这棵满二叉树是否为二叉搜索树(BST)。

  • 第 1 步很好做,循环处理一下即可;
  • 第 2 步,根据满二叉树的性质,如果根的下标为 i,则左孩子为 2*i,右孩子为 2*i+1利用这个性质可以进行递归构造这棵二叉树;
  • 这道题的难点在于第 3 步,即如何判断一棵树为 BST 呢?刚开始我写出了这样的代码:
    def judgeBST(self, root):
        if not root:
            return True
        if root.left and root.left.val > root.val:
            return False
        if root.left and root.right.val < root.val:
            return False
        return self.judgeBST(root.left) and self.judgeBST(root.right)

但是,最终通过了 90%,有一个 case 没有通过:10,5,15,3,11,13,18,把它画成满二叉树之后,它不是 BST,应该返回 False,但是上面这个代码返回了 True。分析原因发现,上述代码只能判断每棵子树满足 BST 的条件,但是全局 BST 可能就不满足了(11 > 10)。具体的错误原因可以参考下面这篇博客,写得很清楚:

判断一棵树是否是二叉搜索树

实际上,我们可以利用 BST 的性质:中序遍历是递增的 进行判断。

使用中序遍历的方法实现:

  • 对树进行中序遍历,将结果保存在 temp 数组中;
  • 检测 temp 数组是否为升序排列,如果是,则为 BST,反之则不是。

此方法还可以进一步的优化,不用 temp 数组,避免使用额外的内存开销。在中序遍历时使用一个全局变量 pre 保存前驱节点,如果当前节点的值小于前驱节点的值 pre.val,则该树不是 BST。

完整代码 Python3 实现:
class TreeNode:    # 定义树结构
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

class Solution:
    
    def _input(self):    # 处理输入
        li = []
        for num in input().split(','):
            if num == 'None':
                li.append(None)
            else:
                li.append(int(num))
        return [0] + li    # 下标从 1 开始,便于接下来二叉树的构造
    
    def construct(self, li, pos):    # 根据列表 li 递归构造二叉树,pos 为 li 的索引位置
        if pos >= len(li) or li[pos] == None:
            return None
        node = TreeNode(li[pos])
        node.left = self.construct(li, 2*pos)
        node.right = self.construct(li, 2*pos+1)
        return node
    
    def judgeBST(self, root):    # 利用 BST 中序遍历递增的性质判断是否为 BST
        if not root:
            return True
        if not self.judgeBST(root.left):
            return False
        if self.pre != None and self.pre.val > root.val:
            return False
        self.pre = root
        if not self.judgeBST(root.right):
            return False
        return True
    
    def ans(self):    # 返回结果
        li = self._input()
        root = self.construct(li, 1)
        self.pre = None    # 全局遍历 self.pre,保存树的前驱结点
        return self.judgeBST(root)

print(Solution().ans())    # 调用函数,输出结果

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 判断二叉树是否为二叉搜索树

    这题利用二叉搜索树的特性:左子树的所有的关键字小于根节点的关键字,右子树的所有关键字都大于根结点 的关键字。二叉搜索树的中序遍历一定是个有序序列。根据这一特性可...

    AI那点小事
  • 判断是不是一棵二叉搜索树!

    题目地址:https://leetcode-cn.com/problems/validate-binary-search-tree/

    代码随想录
  • 判断一棵树是否为完全二叉树

    例如下图所示的情况,当遍历到红色节点后,由于其只有左孩子,没有右孩子,因此实际上认为当前开启了一个状态,这个状态的开启,使得接下来的所有节点必须只能是叶子节点,...

    mathor
  • 判断一棵树是否为二叉排序树

    由于二叉排序树的中序遍历时得到的一定是个一个升序序列,我们可以根据这一性质,利用中序遍历进行判定。

    AI那点小事
  • 2021-04-12:判断二叉树是否是搜索二叉树?

    福大大架构师每日一题
  • 判断一个树是否为平衡二叉树&&二分搜索树 && 完全二叉树

    只要中序遍历是递增的就是搜索二叉树。这里采用的是前面文章采用的二叉树非递归的方式遍历的方法。

    大学里的混子
  • 二叉树的常用算法递归2 非递归3 小结4 实战coding5序列化和反序列化判断一棵二叉树是否是平衡二叉树判断一棵树是否是搜索二叉树、判断一棵树是否是完全二叉树

    JavaEdge
  • 2021-04-14:判断二叉树是否是满二叉树?

    网上查到的答案,一般会计算树的高度。我的答案不需要计算树的高度,至于是否准确,不得而知。

    福大大架构师每日一题
  • 判断二叉树是否为平衡二叉树

    解题思路: 根据二叉树的定义,我们可以递归遍历二叉树的每一个节点来,求出每个节点的左右子树的高度,如果每个节点的左右子树的高度相差不超过1,按照定义,它就是...

    Dabelv
  • 04-树4 是否同一棵二叉搜索树 (25分)

    给定一个插入序列就可以唯一确定一棵二叉搜索树。然而,一棵给定的二叉搜索树却可以由多种不同的插入序列得到。例如分别按照序列{2, 1, 3}和{2, 3, 1}插...

    AI那点小事
  • 数据结构之判断一棵树是否为完全二叉树

    版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/sinat_35512245/articl...

    大黄大黄大黄
  • 是否为同一二叉搜索树

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。 ...

    喜欢ctrl的cxk
  • LeetCode 98 | 判断二叉搜索树是否合法

    今天是LeetCode专题第63篇文章,我们一起来聊聊LeetCode中的第98题,二叉搜索树的合法性判断问题。和之前介绍过的几道题类似,也是一道关于二叉搜索树...

    TechFlow-承志
  • 判断是否为完全二叉树

    李志伟
  • 2-1 是否同一棵二叉搜索树 (35 分)

    给定一个插入序列就可以唯一确定一棵二叉搜索树。然而,一棵给定的二叉搜索树却可以由多种不同的插入序列得到。例如分别按照序列{2, 1, 3}和{2, 3, 1}插...

    韩旭051
  • 【算法】搜索二叉树,完全二叉树,平衡二叉树的判断

    它的左子树不空,则左子树上所有结点的值均小于它的根结点的值; 若它的右子树不空,则右子树上所有结点的值均大于它的根结点的值;

    MapleYe
  • 剑指offer代码解析——面试题24二叉搜索树的后序遍历序列

    本题有bug,欢迎大神指教! /** * 题目:输入一个整数数组,判断该数组书不是某二叉搜索数的后序遍历的结果。如果是返回true,否则返回false。假设输...

    大闲人柴毛毛
  • 2021-04-13:判断二叉树是否是平衡二叉树?

    福大大架构师每日一题
  • 2021-04-11:判断二叉树是否是完全二叉树?

    福大大架构师每日一题

扫码关注云+社区

领取腾讯云代金券