判斷一棵滿二叉樹是否為二叉搜索樹
- 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()) # 調用函數，輸出結果
