更多精彩內(nèi)容列另，請關(guān)注【力扣簡單題】。
樹是一種重要的數(shù)據(jù)結(jié)構(gòu)旦装，而二叉樹是其中的重點和難點页衙，有關(guān)二叉樹的基礎(chǔ)知識，讀者可移步【二叉樹基礎(chǔ)】查看更多內(nèi)容阴绢。這里店乐，我們重點講述樹的基本結(jié)構(gòu)在python中是如何構(gòu)建和應(yīng)用的。
1. 二叉樹的結(jié)點
二叉樹的結(jié)點有三個實例變量：
- 結(jié)點值呻袭，可以是任意數(shù)據(jù)類型眨八，但是以整數(shù)最為簡單；
- 左孩子左电，為二叉樹節(jié)點廉侧，如果沒有則設(shè)置為None。
- 右孩子篓足，為二叉樹節(jié)點段誊，如果沒有則設(shè)置為None。
每個結(jié)點在實例化時栈拖，都需要設(shè)置該結(jié)點的值连舍，并且該結(jié)點默認左右孩子均為None，需要通過賦值語句進行添加辱魁。
class TreeNode:
"""
二叉樹的結(jié)點
"""
def __init__(self, x):
self.val = x # 結(jié)點值
self.left = None # 左孩子
self.right = None # 右孩子
2. 二叉樹的構(gòu)建
這里烟瞧，我們設(shè)計一個函數(shù)，通過一個列表構(gòu)建一棵二叉樹染簇，輸入的列表按照二叉樹的層次順序給出各個元素参滴，我們根據(jù)二叉樹的下標尋找結(jié)點之間的對應(yīng)關(guān)系：下標為i的結(jié)點的左右孩子在列表中的下標分別是2i+1和2i+2。
def create_tree(nodes):
"""
根據(jù)列表構(gòu)建一棵二叉樹
:param nodes: 層次遍歷序列
:return: 二叉樹的根節(jié)點
"""
def helper(node, i): # 用列表遞歸創(chuàng)建二叉樹锻弓，
if i < len(nodes): # 當下標索引滿足條件時
if nodes[i] in ['#', None]: # 如果列表中下標為i的結(jié)點為空
return None # 返回None
else:
node = TreeNode(nodes[i]) # 構(gòu)建當前結(jié)點
node.left = helper(node.left, 2 * i + 1) # 構(gòu)建左子樹砾赔，通過下標查找
node.right = helper(node.right, 2 * i + 2) # 構(gòu)建右子樹，通過下標查找
return node # 返回根節(jié)點為下標為i的元素的子樹
return node # 返回根節(jié)點
root = TreeNode(0) # 臨時結(jié)點
root = helper(root, 0) # 建立樹
return root # 返回樹的根節(jié)點
假設(shè)我們要構(gòu)建一棵滿二叉樹：
1
/ \
2 3
/ \ / \
4 5 6 7
我們只需要調(diào)用該函數(shù)即可：
root = create_binary_tree([1, 2, 3, 4, 5, 6, 7])
如果我們需要構(gòu)建一棵普通二叉樹青灼，例如：
1
/ \
2 3
/ /
4 6
我們將為空的葉子結(jié)點填充為None或“#”暴心，最后一層的最后幾個結(jié)點如果為連續(xù)的空結(jié)點，可以不做操作杂拨。
root = create_binary_tree([1, 2, 3, 4, None, 6])
3. 二叉樹的遍歷
二叉樹常見的遍歷方式有四種专普，前序遍歷、中序遍歷弹沽、后序遍歷以及層次遍歷檀夹，有關(guān)遍歷順序的基礎(chǔ)知識可以參考【二叉樹的遍歷】筋粗，每一種遍歷又可以通過遞歸和迭代兩種方式實現(xiàn)。
舉個栗子炸渡，對于一棵滿二叉樹娜亿，我們分別使用前序、中序蚌堵、后序和層序打印方式买决，結(jié)果為：
1
/ \
2 3
/ \ / \
4 5 6 7
前序：[1, 2, 4, 5, 3, 6, 7]
中序：[4, 2, 5, 1, 6, 3, 7]
后序：[4, 5, 2, 6, 7, 3, 1]
層序：[1, 2, 3, 4, 5, 6, 7]
遞歸實現(xiàn)
遍歷的遞歸實現(xiàn)要更簡潔易懂一些，無需借助棧吼畏、隊列等額外數(shù)據(jù)結(jié)構(gòu)督赤，前序、中序和后序的遍歷順序有十分類似的實現(xiàn)方式宫仗，唯一的區(qū)別在于根節(jié)點與左右孩子之間的順序關(guān)系：
如果輸入空樹够挂，直接返回空列表；
如果輸入不是空樹藕夫，獲得當前結(jié)點的值并存放在列表中孽糖，遞歸調(diào)用本函數(shù)獲得左子樹和右子樹的遍歷結(jié)果：
（1）前序遍歷：根節(jié)點+左子樹+右子樹；
（2）中序遍歷：左子樹+根節(jié)點+右子樹毅贮；
（3）后序遍歷：左子樹+右子樹+根節(jié)點办悟。
1. 前序遍歷
def pre_order(node):
"""
前序遍歷
:param node: 二叉樹的根節(jié)點
:return: 遍歷結(jié)果列表
"""
if not node:
return []
return [node.val] + pre_order(node.left) + pre_order(node.right)
2. 中序遍歷
def in_order(node):
"""
中序遍歷
:param node: 二叉樹的根節(jié)點
:return: 遍歷結(jié)果列表
"""
if not node:
return []
return pre_order(node.left) + [node.val] + pre_order(node.right)
3. 后序遍歷
def post_order(node):
"""
后序遍歷
:param node: 二叉樹的根節(jié)點
:return: 遍歷結(jié)果列表
"""
if not node:
return []
return pre_order(node.left) + pre_order(node.right) + [node.val]
我們可以考慮把以上三種遍歷方式用python中的lambda表達式進行快速定義，只需要一句話定義一個函數(shù)：
# 前序遍歷
pre_order = lambda node: [node.val] + pre_order(node.left) + pre_order(node.right) if node else []
# 中序遍歷
in_order = lambda node: in_order(node.left) + [node.val] + in_order(node.right) if node else []
# 后序遍歷
post_order = lambda node: post_order(node.left) + post_order(node.right) + [node.val] if node else []
4. 層序遍歷
我們借助列表實現(xiàn)層序遍歷滩褥。我們將層序遍歷的結(jié)果用列表嵌套結(jié)構(gòu)表示病蛉，并且列表中的每個元素是每一層的遍歷結(jié)果，也是列表形式瑰煎。在遞歸調(diào)用時铺然，我們構(gòu)建助手函數(shù)（helper），用于將數(shù)中某一層的某結(jié)點添加到指定層的結(jié)果列表當中酒甸。
def level_order(root):
"""
層序遍歷
:type root: TreeNode
:rtype: List[List[int]]
"""
def helper(node, level):
"""
將以node為根節(jié)點的樹的層次遍歷結(jié)果添加到res中
:param node: 根節(jié)點
:param level: 根節(jié)點所在的層次
:return:
"""
if not node: # 如果根節(jié)點為空
return # 跳出
else:
res[level-1].append(node.val) # 將根節(jié)點的值添加到所在層的結(jié)果列表中
if len(res) == level: # 遍歷到新層時魄健，只有最左邊的結(jié)點使得等式成立
res.append([]) # 添加下一層
helper(node.left, level+1) # 遍歷左孩子
helper(node.right, level+1) # 遍歷右孩子
res = [[]] # 默認層序遍歷結(jié)果為空列表
helper(root, 1) #
return res[:-1] # 去掉最后一層結(jié)束時添加的
迭代實現(xiàn)
迭代實現(xiàn)要比遞歸實現(xiàn)更加復雜，使用迭代法實現(xiàn)二叉樹的遍歷需要借助隊列或棧等數(shù)據(jù)結(jié)構(gòu)插勤。
前序沽瘦、中序和后續(xù)遍歷都要用到棧的數(shù)據(jù)結(jié)構(gòu)，它們有共同的循環(huán)控制條件农尖，即當棧與當前結(jié)點均為空時跳出循環(huán)析恋，在循環(huán)內(nèi)部，針對當前結(jié)點是否為空的情況也有不同的操作：
前序遍歷：當前結(jié)點不為空記錄當前結(jié)點值盛卡，并把右結(jié)點入棧助隧，更新當前結(jié)點為左孩子，當前結(jié)點為空時更新為棧頂結(jié)點滑沧；
中序遍歷：當前結(jié)點不為空并村，則結(jié)點入棧漏健，并更新為左孩子，當前結(jié)點為空時更新為棧頂結(jié)點橘霎，記錄當前結(jié)點值并更新為右孩子；
后序遍歷：當前結(jié)點不為空殖属，則記錄結(jié)點值姐叁，左孩子入棧，當前結(jié)點更新為右孩子洗显，若節(jié)點為空則更新為棧頂結(jié)點外潜。
1. 前序遍歷
def pre_order(root):
"""
前序遍歷
:param root: 二叉樹的根節(jié)點
:return: 遍歷結(jié)果列表
"""
stack = [] # 構(gòu)造空棧
res = [] # 結(jié)果列表
cur = root # 當前結(jié)點
while stack or cur: # 如果棧和當前結(jié)點均為空時跳出循環(huán)
if cur: # 如果當前結(jié)點不為空
res.append(cur.val) # 則添加當前結(jié)點的值到結(jié)果列表中
stack.append(cur.right) # 把右子樹放進棧中
cur = cur.left # 更新當前結(jié)點為左子樹
else: # 如果當前結(jié)點為空
cur = stack.pop() # 從棧中彈出結(jié)點
return res # 返回結(jié)果列表
2. 中序遍歷
def in_order(root):
"""
中序遍歷
:param root:
:return:
"""
stack = [] # 構(gòu)造空棧
res = [] # 結(jié)果列表
cur = root # 當前結(jié)點
while stack or cur: # 如果棧和當前結(jié)點均為空時跳出循環(huán)
if cur: # 如果當前結(jié)點不為空
stack.append(cur) # 首先將當前結(jié)點放入棧中
cur = cur.left # 更新當前結(jié)點為左孩子
else: # 如果當前結(jié)點為空
cur = stack.pop() # 從棧中彈出元素
res.append(cur.val) # 結(jié)果列表中添加當前結(jié)點的值
cur = cur.right # 更新當前結(jié)點為右孩子
return res # 返回結(jié)果列表
3. 后序遍歷
def post_order(root):
"""
后續(xù)遍歷
:param root:
:return:
"""
stack = [] # 構(gòu)造空棧
res = [] # 結(jié)果列表
cur = root # 當前結(jié)點
while stack or cur: # 如果棧和當前結(jié)點均為空時跳出循環(huán)
if cur: # 如果當前結(jié)點不為空
res.append(cur.val) # 當前結(jié)點值添加到結(jié)果列表
stack.append(cur.left) # 左孩子入棧
cur = cur.right # 更新當前結(jié)點為右孩子
else: # 如果當前結(jié)點為空
cur = stack.pop() # 彈出右孩子
return res[::-1] # 結(jié)果列表逆序輸出
4. 層序遍歷
層次遍歷需要使用隊列，每次將結(jié)點出隊挠唆，記錄該結(jié)點值并將其左右孩子依次入隊处窥，直到隊列中沒有結(jié)點為止。
def level_order(root):
if not root: # 如果輸入空樹
return [] # 返回空列表
res = [] # 結(jié)果列表
cur = root # 當前結(jié)點
queue = [cur] # 當前結(jié)點入隊
while queue: # 只要隊列不為空
cur = queue.pop(0) # 元素出隊
res.append(cur.val) # 添加當前結(jié)果
if cur.left: # 如果左子樹不為空
queue.append(cur.left) # 左孩子入隊
if cur.right: # 如果右子樹不為空
queue.append(cur.right) # 右孩子入隊
return res # 返回結(jié)果列表
“之”字形打印二叉樹
這是二叉樹的層次遍歷的一種操作玄组，和普通的層次遍歷不同滔驾，我們對偶數(shù)行二叉樹的層結(jié)果進行逆序即可。這里為大家提供一種便于理解的方式：
import create_binary_tree # 引入上文中提到的構(gòu)建二叉樹的函數(shù)俄讹，如果在同一個py文件中則不必
def get_layers(root, switch=True):
"""
按層打印二叉樹
:param pRoot: 輸入二叉樹的根節(jié)點
:param switch: “之”字形打印開關(guān)哆致，如果打開，則按“之”字形打印患膛，否則每一層從左到右打印
:return: 返回結(jié)果列表摊阀，其中的每個元素也是列表，代表了每一層的結(jié)點值
"""
if not root: # 如果輸入空樹
return [] # 返回空列表
cur_layer = [root] # 當前層結(jié)點
result = [] # 結(jié)果列表
right2left = False # 方向標志踪蹬，默認從左到右打印
while cur_layer: # 如果當前層有結(jié)點
cur_val = [] # 當前層的值
next_layer = [] # 下一層結(jié)點
for node in cur_layer: # 遍歷當前層的每一個結(jié)點
cur_val.append(node.val) # 獲得當前結(jié)點層的值
if node.left: # 如果左子孩子不為空
next_layer.append(node.left) # 將左孩子添加到下一層結(jié)點列表中
if node.right: # 如果右孩子不為空
next_layer.append(node.right) # 將右孩子添加到當前結(jié)點中
if right2left: # 如果要求從右到左打印
cur_val.reverse() # 將當前層結(jié)點值列表逆序
if cur_val: # 如果當前層結(jié)點值列表不為空
result.append(cur_val) # 添加到最終結(jié)果中
cur_layer = next_layer # 更新當前層為下一層列表
if switch: # 如果打開了“之”字形打印開關(guān)
right2left = not right2left # 每輪循環(huán)翻轉(zhuǎn)方向標志
return result # 返回最終結(jié)果
if __name__ == "__main__":
# 測試代碼
s = Solution()
r = create_binary_tree([1,2,3,4,5,6,7])
print(get_layers(r))
# 結(jié)果：[[1], [3, 2], [4, 5, 6, 7]]
這里通過不斷翻轉(zhuǎn)變量（right2left）的布爾值實現(xiàn)相鄰層的打印順序不同胞此，并在函數(shù)開始設(shè)置開關(guān)（switch）來決定是否需要進行“之”字形打印，讀者可以嘗試關(guān)閉這個開關(guān)跃捣，那么實驗的結(jié)果就與層次遍歷無異漱牵。
4. 二叉樹的序列化和反序列化
對于所有結(jié)點都是整數(shù)的二叉樹，我們可以用一個字符串去代表這棵樹枝缔，這個過程叫做二叉樹的序列化布疙，根據(jù)代表一棵樹的字符串序列重構(gòu)出這棵樹的過程即為二叉樹的反序列化。序列化和反序列化互為逆過程愿卸，類似二叉樹的遍歷與二叉樹的構(gòu)建互為逆過程灵临。這里需要保持兩個一致：
遍歷順序一致：如果序列化二叉樹時采用前序遍歷方式，則重構(gòu)二叉樹依舊需要依照前序遍歷順序重構(gòu)趴荸；
主要字符對應(yīng)：如果序列化二叉樹時空結(jié)點用“#”表示儒溉，那么重構(gòu)二叉樹時遇到“#”時應(yīng)該構(gòu)造空結(jié)點。
1. 二叉樹的序列化
二叉樹的序列化過程使用遞歸很簡單发钝，我們可以采用遞歸前序遍歷方式實現(xiàn)：
def serialize(root):
"""
二叉樹的序列化
:param root:
:return:
"""
if not root:
return "#"
return str(root.val) + ',' + serialize(root.left) + ',' + serialize(root.right)
2. 二叉樹的反序列化
與上述序列化過程類似顿涣，我們采用前序遍歷方式重建二叉樹波闹。
def deserialize(s):
"""
二叉樹的反序列化
:param s:
:return:
"""
def helper(nodes):
if not nodes:
return None
val = nodes.pop(0) # 取出第一個元素
if val == '#': # 如果該元素為“#”
node = None # 則當前結(jié)點為空
else: #
node = TreeNode(int(val)) # 實例化當前結(jié)點
node.left = helper(nodes) # 構(gòu)建左子樹
node.right = helper(nodes) # 構(gòu)建右子樹
return node # 返回當前結(jié)點
nodes = s.split(',') # 劃分成列表
return helper(nodes) # 反序列化
5. 二叉樹的屬性
1. 二叉樹的最大深度
從根結(jié)點到葉結(jié)點依次經(jīng)過的結(jié)點（含根、葉結(jié)點）形成樹的一條路徑涛碑，最長路徑的長度為樹的深度精堕。尋找二叉樹的最大深度。
這道題在力扣中對應(yīng)的題目是【題目104. 二叉樹的最大深度】這里我們采用遞歸法和迭代法兩種方式解決這個問題蒲障。遞歸法實際上是在獲取所有結(jié)點所在層次的最大值：
def max_depth(root):
"""
遞歸法獲得二叉樹的最大深度
:param root:
:return:
"""
if not root: # 如果輸入空樹
return 0 # 最大深度為零
max_left = max_depth(root.left) # 獲得左子樹最大深度
max_right = max_depth(root.right) # 獲得右子樹最大深度
return max(max_left, max_right) + 1 # 左右子樹的最大深度加上根節(jié)點歹篓，即為當前子樹最大深度
迭代法類似層序遍歷，只是這里不需要記錄各層結(jié)點揉阎，只需要統(tǒng)計達到的層次：
def get_depth(root):
"""
獲得二叉樹的深度
:param root: 輸入二叉樹的根節(jié)點
:return: 返回二叉樹的深度
"""
if not root: # 如果輸入結(jié)點為空
return 0 # 則最大深度為零
cur_layer = [root] # 當前層結(jié)點列表
depth = 0 # 初始深度為零
while cur_layer: # 如果當前層存在結(jié)點庄撮，則執(zhí)行
next_layer = [] # 初始化下一層結(jié)點列表
for node in cur_layer: # 遍歷當前層每一個結(jié)點
if node.left: # 如果當前結(jié)點存在左孩子
next_layer.append(node.left) # 將左孩子添加到下一層結(jié)點列表
if node.right: # 如果當前結(jié)點存在右孩子
next_layer.append(node.right) # 將右孩子添加到下一層結(jié)點列表
cur_layer = next_layer # 更新當前結(jié)點列表為下一層結(jié)點列表
depth += 1 # 深度+1
return depth # 返回最大深度
測試用例：
if __name__ == "__main__":
r = create_binary_tree([1, 2, 3, 4, 5, 6, 7])
print(max_depth(r))
# 答案：3
2. 二叉樹的最小深度
最小深度是從根節(jié)點到最近葉子節(jié)點的最短路徑上的節(jié)點數(shù)量。這道題來源于【111. 二叉樹的最小深度】毙籽，解法與上題類似洞斯，這里，我們使用遞歸實現(xiàn)坑赡，更加便捷：
def min_depth(root):
"""
二叉樹的最小深度
:param root: 二叉樹的根節(jié)點
:return: 二叉樹的最小深度
"""
if not root: # 如果輸入空樹
return 0 # 返回最小深度零
left_min_depth = min_depth(root.left) # 調(diào)用本函數(shù)獲得左子樹的最小深度
right_min_depth = min_depth(root.right) # 調(diào)用本函數(shù)獲得右子樹的最小深度
if left_min_depth > 0 and right_min_depth > 0: # 如果左右子樹最小深度都不是0
res = min(left_min_depth, right_min_depth) + 1 # 當前子樹的最小深度是兩者較小值+1
else: # 如果有一個子樹是空
res = max(left_min_depth, right_min_depth) + 1 # 當前數(shù)的最小深度取決于非空子樹烙如，其深度+1
return res
測試用例：
if __name__ == "__main__":
r = create_binary_tree([1, 2, 3, 4, 5, 6, 7])
print(min_depth(r))
# 答案：3
3. 所有路徑
本題來源【257. 二叉樹的所有路徑】，具體解法可以查看毅否。
def get_paths(root):
"""
找到以root為根節(jié)點的二叉樹的所有路徑
:type root: 根節(jié)點
:rtype: 所有路徑厅翔，列表嵌套形式給出
"""
def helper(root, path, res):
"""
助手
:param root: 根節(jié)點
:param path: 遍歷到root為止的當前路徑
:param res: 最終結(jié)果
:return:
"""
cur_path = path + [root.val] # 當前路徑
if not root.left and not root.right: # 如果輸入是葉子結(jié)點
res.append(cur_path) # 把路徑添加到結(jié)果
return # 返回
if root.left: # 如果存在左孩子
helper(root.left, cur_path, res) # 考慮左孩子
if root.right: # 如果存在右孩子
helper(root.right, cur_path, res) # 考慮右孩子
if not root: # 如果輸入空樹
return [] # 不存在路徑，返回空列表
paths = [] # 最終結(jié)果
helper(root, [], paths) # 尋找路徑
return paths # 返回結(jié)果
測試用例：
if __name__ == "__main__":
r = create_binary_tree([1, 2, 3, 4, 5, 6, 7])
print(min_depth(r))
# 結(jié)果：[[1, 2, 4], [1, 2, 5], [1, 3, 6], [1, 3, 7]]
4. 對稱二叉樹
本題源于【101. 對稱二叉樹】搀突，用函數(shù)判斷二叉樹是否是鏡像二叉樹刀闷。如果左右子樹鏡像對稱，那么二叉樹也鏡像對稱仰迁。
def isSymmetric(root):
"""
遞歸判斷是否鏡像對稱
:param root:
:return:
"""
def is_mirror(p, q): # 判斷左右子樹是否鏡像對稱
if not p and not q: # 如果左右子樹均為空
return True # 鏡像對稱
elif not p and q or p and not q: # 如果有且只有一棵子樹為空
return False # 一定不對稱
else: # 如果兩棵子樹都不為空
# 兩棵樹鏡像對稱的條件：根節(jié)點值相等甸昏，左左孫子和右右孫子鏡像對稱，左右孫子和右左孫子鏡像對稱
return p.val == q.val and is_mirror(p.left, q.right) and is_mirror(p.right, q.left)
return is_mirror(root, root) # 判別自身與自身是否鏡像對稱
測試用例：
if __name__ == '__main__':
r = create_binary_tree([1, 2, 3, 4, 5, 6, 7])
print(is_symmetric(r))
# 測試結(jié)果：False
5. 二叉樹的操作
1. 二叉樹的鏡像
將二叉樹轉(zhuǎn)為其鏡像二叉樹徐许。需要將根節(jié)點的左右子樹交換施蜜，然后將左右子樹轉(zhuǎn)為其鏡像樹即可。
def mirror(root):
"""
將二叉樹逆轉(zhuǎn)
:param root:
:return:
"""
if root:
root.left, root.right = root.right, root.left # 左右子樹交換
mirror(root.left) # 左右子樹鏡像
mirror(root.right)
測試用例：
if __name__ == '__main__':
r = create_binary_tree([1, 2, 3, 4, 5, 6, 7])
print(get_layers(r, False)) # 上文中的“之”字形遍歷的層次遍歷用法
mirror(r)
print(get_layers(r, False))
# 測試結(jié)果：[[1], [2, 3], [4, 5, 6, 7]]雌隅， [[1], [3, 2], [7, 6, 5, 4]]
6. 整合
我們將上述代碼整合翻默，構(gòu)建一個實例化的二叉樹：
class BinaryTree:
def __init__(self, node_vals):
self.tree = create_binary_tree(node_vals)
@staticmethod # 靜態(tài)方法
def create_binary_tree(nodes):
def helper(node, i):
if i < len(nodes):
if nodes[i] in ['#', None]:
return None
else:
node = TreeNode(nodes[i])
node.left = helper(node.left, 2 * i + 1)
node.right = helper(node.right, 2 * i + 2)
return node
return node
root = TreeNode(0)
root = helper(root, 0)
return root
# 獲取序列化結(jié)果
@property
def serialize(self):
s = lambda r: str(r.val) + ',' + s(r.left) + ',' + s(r.right) if r else "#"
return s(self.tree)
# 獲取前序遍歷結(jié)果，以列表形式返回
@property
def pre_order(self):
helper = lambda n: [n.val] + helper(n.left) + helper(n.right) if n else []
return helper(self.tree)
# 獲取中序遍歷結(jié)果恰起，以列表形式返回
@property
def in_order(self):
helper = lambda n: helper(n.left) + [n.val] + helper(n.right) if n else []
return helper(self.tree)
# 獲取后序遍歷結(jié)果修械，以列表形式返回
@property
def post_order(self):
helper = lambda n: helper(n.left) + helper(n.right) + [n.val] if n else []
return helper(self.tree)
# 層序遍歷，以嵌套列表形式返回
@property
def level_order(self):
def helper(node, level):
if not node:
return
else:
res[level - 1].append(node.val)
if len(res) == level:
res.append([])
helper(node.left, level + 1)
helper(node.right, level + 1)
res = [[]]
helper(self.tree, 1)
return res[:-1]
# 獲取二叉樹的最大深度
@property
def max_depth(self):
helper = lambda r: max(helper(r.left), helper(r.right))+1 if r else 0
return helper(self.tree)
# 獲取二叉樹的最小深度
@property
def min_depth(self):
def helper(root):
if not root:
return 0
left_min_depth = helper(root.left)
right_min_depth = helper(root.right)
if left_min_depth > 0 and right_min_depth > 0:
res = min(left_min_depth, right_min_depth) + 1
else:
res = max(left_min_depth, right_min_depth) + 1
return res
return helper(self.tree)
# 獲取二叉樹的所有路徑
@property
def all_paths(self):
def helper(root, path, res):
cur_path = path + [root.val]
if not root.left and not root.right:
res.append(cur_path)
return
if root.left:
helper(root.left, cur_path, res)
if root.right:
helper(root.right, cur_path, res)
if not self.tree:
return []
paths = []
helper(self.tree, [], paths)
return paths
# 判斷二叉樹是否鏡像對稱
@property
def is_symmetric(self):
def helper(p, q):
if not p and not q:
return True
elif not p and q or p and not q:
return False
else:
return p.val == q.val and helper(p.left, q.right) and helper(p.right, q.left)
return helper(self.tree, self.tree)
# 將二叉樹鏡像翻轉(zhuǎn)
def flip(self):
def helper(root):
if root:
root.left, root.right = root.right, root.left
helper(root.left)
helper(root.right)
helper(self.tree)
裝飾符@property表示類屬性检盼，測試用例為：
if __name__ == '__main__':
nodes = [1, 2, 3, 4, 5, 6, 7, 8]
print('構(gòu)造一棵二叉樹肯污，其結(jié)點列表為：{}.'.format(nodes))
bt = BinaryTree(nodes)
print('二叉樹的序列化結(jié)果為：{}'.format(bt.serialize))
print('二叉樹的前序遍歷結(jié)果為：{}'.format(bt.pre_order))
print('二叉樹的中序遍歷結(jié)果為：{}'.format(bt.in_order))
print('二叉樹的后序遍歷結(jié)果為：{}'.format(bt.post_order))
print('二叉樹的層序遍歷結(jié)果為：{}'.format(bt.level_order))
print('二叉樹的最大深度結(jié)果為：{}'.format(bt.max_depth))
print('二叉樹的最小深度結(jié)果為：{}'.format(bt.min_depth))
print('二叉樹的所有路徑結(jié)果為：{}'.format(bt.all_paths))
print('二叉樹的為鏡像對稱：{}'.format(bt.is_symmetric))
print('將二叉樹左右翻轉(zhuǎn)')
bt.flip()
print('翻轉(zhuǎn)后二叉樹的層序遍歷結(jié)果為：{}'.format(bt.level_order))
這棵二叉樹[1, 2, 3, 4, 5, 6, 7, 8]實際上是：
1
/ \
2 3
/ \ / \
4 5 6 7
/
8
測試結(jié)果為：
二叉樹的序列化結(jié)果為：1,2,4,8,#,#,#,5,#,#,3,6,#,#,7,#,#
二叉樹的前序遍歷結(jié)果為：[1, 2, 4, 8, 5, 3, 6, 7]
二叉樹的中序遍歷結(jié)果為：[8, 4, 2, 5, 1, 6, 3, 7]
二叉樹的后序遍歷結(jié)果為：[8, 4, 5, 2, 6, 7, 3, 1]
二叉樹的層序遍歷結(jié)果為：[[1], [2, 3], [4, 5, 6, 7], [8]]
二叉樹的最大深度結(jié)果為：4
二叉樹的最小深度結(jié)果為：3
二叉樹的所有路徑結(jié)果為：[[1, 2, 4, 8], [1, 2, 5], [1, 3, 6], [1, 3, 7]]
二叉樹的為鏡像對稱：False
將二叉樹左右翻轉(zhuǎn)
翻轉(zhuǎn)后二叉樹的層序遍歷結(jié)果為：[[1], [3, 2], [7, 6, 5, 4], [8]]
如有疑問或建議，歡迎評論區(qū)留言~
