给定一棵二叉树,已经其中没有重复值的节点,请判断该二叉树是否为搜索二叉树和完全二叉树。
输入:{2,1,3}
返回值:true,true
它的左子树不空,则左子树上所有结点的值均小于它的根结点的值;
若它的右子树不空,则右子树上所有结点的值均大于它的根结点的值;
总之:二叉搜索树中,左子树都比其根节点小,右子树都比其根节点大,递归定义。
重点来了!二叉搜索树的中序遍历一定是从小到大排序的。
若设二叉树的深度为h,除第 h 层外,其它各层 (1~h-1) 的结点数都达到最大个数,第 h 层所有的结点都连续集中在最左边。
经典应用:堆
完全二叉树由满二叉树转化而来,也就是将满二叉树从最后一个节点开始删除,一个一个从后往前删除,剩下的就是完全二叉树。
# 思路:利用递归进行中序遍历,通过判断中序遍历序列是否有序来判定是否为搜索二叉树
def isBSTmidTravelsal(self,root):
res = []
def dfs(root):
nonlocal res
if not root:
return
dfs(root.left)
res.append(root.val)
dfs(root.right)
dfs(root)
return res==sorted(res)
# 层次遍历
# 使用队列,每移除一个节点就向队列添加左右节点,当遇到None时判断当前队列是否全是None,如果队列中除了None还有其它值则表示当前节点之后的节点还有左右子树即不是完全性二叉树。
def isCBT(self,root):
q= [root]
while q:
for i in range(len(q)):
node=q.pop(0)
if node is None:
if set(q)=={None}:
return True
else:
return False
# 注意这里的空节点也要进队,因此不需要进行层次序列的空节点判断
# if node.left:
q.append(node.left)
# if node.right:
q.append(node.right)
# newcoder完整代码
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
#
#
# @param root TreeNode类 the root
# @return bool布尔型一维数组
#
class Solution:
def judgeIt(self , root ):
return [self.isBSTmidTravelsal(root),self.isCBT(root)]
def isBSTmidTravelsal(self,root):
res = []
def dfs(root):
nonlocal res
if not root:
return
dfs(root.left)
res.append(root.val)
dfs(root.right)
dfs(root)
return res==sorted(res)
def isCBT(self,root):
q= [root]
while q:
for i in range(len(q)):
node=q.pop(0)
if node is None:
if set(q)=={None}:
return True
else:
return False
# if node.left:
q.append(node.left)
# if node.right:
q.append(node.right)
# return True
# write code here
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。