判断一棵满二叉树是否为二叉搜索树
- 2019 年 11 月 2 日
- 筆記
题目描述：
给定一棵满二叉树，判定该树是否为二叉搜索树，是的话打印 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()) # 调用函数，输出结果
