前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >判断一棵满二叉树是否为二叉搜索树

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

作者头像
echobingo
发布2019-11-02 22:07:57
1.2K0
发布2019-11-02 22:07:57
举报
文章被收录于专栏: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 呢?刚开始我写出了这样的代码:
代码语言:javascript
复制
    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 实现:
代码语言:javascript
复制
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())    # 调用函数,输出结果
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 题目描述:
  • 输入描述:
  • 输出描述:
  • 示例1
  • 解题思路:
  • 判断一棵树是否是二叉搜索树
  • 完整代码 Python3 实现:
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档