思想
二叉樹(shù)的核心思想是分治和遞歸蜓竹，特點(diǎn)是遍歷方式。
解題方式常見(jiàn)兩類(lèi)思路：
- 遍歷一遍二叉樹(shù)尋找答案储藐；
- 通過(guò)分治分解問(wèn)題尋求答案俱济；
遍歷分為前中后序，本質(zhì)上是遍歷二叉樹(shù)過(guò)程中處理每個(gè)節(jié)點(diǎn)的三個(gè)特殊時(shí)間點(diǎn)：
- 前序是在剛剛進(jìn)入二叉樹(shù)節(jié)點(diǎn)時(shí)執(zhí)行钙勃；
- 后序是在將要離開(kāi)二叉樹(shù)節(jié)點(diǎn)時(shí)執(zhí)行蛛碌；
- 中序是左子樹(shù)遍歷完進(jìn)入右子樹(shù)前執(zhí)行；
# 前序
1 node
/ \
2 left 3 right
中左右
# 中序
2 node
/ \
1 left 3 right
左中右
# 后序
3 node
/ \
1 left 2 right
左右中
多叉樹(shù)只有前后序列遍歷辖源，因?yàn)橹挥卸鏄?shù)有唯一一次中間節(jié)點(diǎn)的遍歷
題目的關(guān)鍵就是找到遍歷過(guò)程中的位置蔚携，插入對(duì)應(yīng)代碼邏輯實(shí)現(xiàn)場(chǎng)景的目的。
實(shí)例
尋找重復(fù)的子樹(shù) leetcode 652
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
輸入：
TreeNode同木，一棵樹(shù)的根節(jié)點(diǎn)
輸出：
List[TreeNode]浮梢，返回所有重復(fù)的子樹(shù)列表
舉例：
輸入 root = [1,2,3,4,null,2,4,null,null,4]
返回二叉樹(shù)子樹(shù)列表 [[2,4],[4]]
1
/ \
2 3
/ / \
4 2 4
/
4
二叉樹(shù)的數(shù)據(jù)存儲(chǔ)可以使用鏈表跛十，也可以使用數(shù)組彤路，往往數(shù)組更容易表達(dá)，根節(jié)點(diǎn)從 index=1 處開(kāi)始存儲(chǔ)芥映，浪費(fèi) index=0 的位置
left_child = 2 * parent
right_child = 2 * parent + 1
parent = child // 2
分治解
查找重復(fù)子樹(shù)洲尊，要在獲得子樹(shù)詳細(xì)情況的位置進(jìn)行比對(duì)远豺，所以在后續(xù)遍歷的位置比對(duì)是否出現(xiàn)了重復(fù)子樹(shù)。全局一塊內(nèi)存儲(chǔ)存出現(xiàn)過(guò)的子樹(shù)坞嘀。
上例中躯护，全局儲(chǔ)存子樹(shù) []，重復(fù)子樹(shù) []
- 根節(jié)點(diǎn) 1 出發(fā)丽涩，在后續(xù)遍歷的位置進(jìn)行比對(duì)
- 1 遍歷到左子樹(shù) 2棺滞，再到左子樹(shù) 4，左右子樹(shù)都為空矢渊，返回到 2
- 2 的右子樹(shù)為空继准，左子樹(shù) 4，存儲(chǔ)到全局子樹(shù)中 [[4]]矮男，返回到根節(jié)點(diǎn) 1
- 繼續(xù)遍歷 1 的右子樹(shù) 3移必，到 3 的左子樹(shù) 2，再到 2 的左子樹(shù) 4 返回
- 2 的左子樹(shù) 4 存在于全局子樹(shù)毡鉴，重復(fù)子樹(shù)增加 [[4]]崔泵，返回 3
- 繼續(xù)遍歷 3 的右子樹(shù) 4，左右子樹(shù)均為空猪瞬，返回 3
- 3 的左子樹(shù) [2,4] 加入全局存儲(chǔ)子樹(shù)憎瘸，[[4], [2,4]]，右子樹(shù)存在于重復(fù)子樹(shù)不再處理陈瘦，返回根節(jié)點(diǎn) 1
- 1 的左子樹(shù) [2,4] 重復(fù)含思，加入重復(fù)子樹(shù) [[4], [2,4]]，右子樹(shù) [3,2,4,4] 加入全局子樹(shù) [[4], [2,4], [3,2,4,4]]
- 結(jié)束遍歷甘晤，最終返回 [[2,4],[4]]
編碼
from typing import Optional, List
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def find_duplicate_subtrees(root: Optional[TreeNode]) -> List[Optional[TreeNode]]:
# 儲(chǔ)存全局子樹(shù)
subtree, duplicate = {}, []
def serialize(root: Optional[TreeNode]) -> str:
nodes = []
def _traverse(node: Optional[TreeNode]):
if node is None:
nodes.append('#')
return
nodes.append(str(node.val))
_traverse(node.left)
_traverse(node.right)
_traverse(root)
return ','.join(nodes)
def traverse(root: Optional[TreeNode]):
# base 條件含潘，葉子空節(jié)點(diǎn)直接返回
if root is None:
return
traverse(root.left)
traverse(root.right)
# 后序位置做子樹(shù)比對(duì)
serialize_left = serialize(root.left)
serialize_right = serialize(root.right)
if serialize_left not in subtree:
subtree[serialize_left] = 0
else:
subtree[serialize_left] += 1
if subtree[serialize_left] == 1:
duplicate.append(root.left)
if serialize_right not in subtree:
subtree[serialize_right] = 0
else:
subtree[serialize_right] += 1
if subtree[serialize_right] == 1:
duplicate.append(root.right)
traverse(root)
# 過(guò)濾空子樹(shù)
return [e for e in duplicate if e]
def find_duplicate_subtrees_optimize(root: Optional[TreeNode]) -> List[Optional[TreeNode]]:
# 儲(chǔ)存全局子樹(shù)
subtree, duplicate = {}, []
def traverse(root: Optional[TreeNode]) -> str:
# base 條件，葉子空節(jié)點(diǎn)返回占位符
if root is None:
return '#'
left = traverse(root.left)
right = traverse(root.right)
# 后序位置做子樹(shù)比對(duì)
tree = f'{left},{right},{root.val}'
if tree not in subtree:
subtree[tree] = 0
else:
subtree[tree] += 1
if subtree[tree] == 1:
duplicate.append(root)
return tree
traverse(root)
return duplicate
相關(guān)
二叉樹(shù) 0
二叉樹(shù) 1
二叉樹(shù) 2
二叉樹(shù) 3
二叉樹(shù) 4
二叉樹(shù) 5
二叉樹(shù) 6
二叉樹(shù) 7
二叉樹(shù) 8
二叉樹(shù) 9
二叉樹(shù) 10
二叉樹(shù) 11
二叉樹(shù) 12
二叉樹(shù) 13
二叉樹(shù) 14
二叉樹(shù) 15
二叉樹(shù) 16
二叉樹(shù) 17
