題目描述
給定一棵二叉樹，已經其中沒有重複值的節點，請判斷該二叉樹是否為搜尋二叉樹和完全二叉樹。
示例1
輸入：{2,1,3}
傳回值：true,true
基本概念
搜尋二叉樹(Binary Search Tree - BST)
它的左子樹不空，則左子樹上所有結點的值均小于它的根結點的值；
若它的右子樹不空，則右子樹上所有結點的值均大于它的根結點的值；
總之：二叉搜尋樹中，左子樹都比其根節點小，右子樹都比其根節點大，遞歸定義。
重點來了！二叉搜尋樹的中序周遊一定是從小到大排序的。
完全二叉樹(Complete Binary Tree- CBT)
若設二叉樹的深度為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 複制