思想
二叉樹(shù)的核心思想是分治和遞歸，特點(diǎn)是遍歷方式缕坎。
解題方式常見(jiàn)兩類思路：
- 遍歷一遍二叉樹(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í)例
二叉樹(shù)的序列化與反序列化 leetcode 297
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
序列化是將一個(gè)數(shù)據(jù)結(jié)構(gòu)或者對(duì)象轉(zhuǎn)換為連續(xù)的比特位的操作，進(jìn)而可以將轉(zhuǎn)換后的數(shù)據(jù)存儲(chǔ)在一個(gè)文件或者內(nèi)存中香府，同時(shí)也可以通過(guò)網(wǎng)絡(luò)傳輸?shù)搅硪粋€(gè)計(jì)算機(jī)環(huán)境董栽，采取相反方式重構(gòu)得到原數(shù)據(jù)。
序列化：
（1）輸入 TreeNode
（2）輸出一個(gè)二叉樹(shù)序列化的字符串
反序列化：
（1）輸入 str企孩，一個(gè)二叉樹(shù)序列化的字符串
（2）輸出 TreeNode锭碳，基于字符串構(gòu)建二叉樹(shù)，返回根節(jié)點(diǎn)勿璃。
舉例：
輸入 root = [1,2,3,null,null,4,5]
返回二叉樹(shù)字符串 [1,2,3,null,null,4,5]
1
/ \
2 3
/ \
4 5
二叉樹(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
遍歷解
序列化和反序列化是遍歷的過(guò)程，序列化從根節(jié)點(diǎn)遍歷全樹(shù)莲组，將值存入字符串诊胞；反序列化是基于字符串反向推導(dǎo)節(jié)點(diǎn)和左右子樹(shù)。
編碼
from typing import Optional
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
INPLACE = '#'
def serialize_binary_tree(root: Optional[TreeNode]) -> str:
# 儲(chǔ)存樹(shù)的節(jié)點(diǎn)信息
nodes = []
def traverse(node: Optional[TreeNode]):
if node is None:
nodes.append(INPLACE)
return
# 前序位置加入節(jié)點(diǎn)信息
nodes.append(str(node.val))
traverse(node.left)
traverse(node.right)
traverse(root)
return ','.join(nodes)
def deserialize_binary_tree(data: str) -> Optional[TreeNode]:
# 邊界保護(hù)
if not data:
return None
nodes = data.split(',')
def traverse(nodes: list) -> Optional[TreeNode]:
if not nodes:
return None
cur_val = nodes.pop(0)
if cur_val == INPLACE:
return None
root = TreeNode(int(cur_val))
root.left = traverse(nodes)
root.right = traverse(nodes)
return root
return traverse(nodes)
相關(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
