1.理解二叉樹的BFS與DFS
左邊是BFS涩搓，按照層進(jìn)行搜索脖阵；圖右邊是DFS皂股，先一路走到底，然后再回頭搜索命黔。
BFS與DFS
BFS
BFS使用隊(duì)列呜呐，把每個還沒有搜索到的點(diǎn)依次放入隊(duì)列，然后再彈出隊(duì)列的頭部元素當(dāng)做當(dāng)前遍歷點(diǎn)悍募。BFS總共有兩個模板：
如果不需要確定當(dāng)前遍歷到了哪一層蘑辑，BFS模板如下。
while queue 不空：
cur = queue.pop()
for 節(jié)點(diǎn) in cur的所有相鄰節(jié)點(diǎn)：
if 該節(jié)點(diǎn)有效且未訪問過：
queue.push(該節(jié)點(diǎn))
如果要確定當(dāng)前遍歷到了哪一層坠宴，BFS模板如下洋魂。
這里增加了level表示當(dāng)前遍歷到二叉樹中的哪一層了，也可以理解為在一個圖中喜鼓，現(xiàn)在已經(jīng)走了多少步了副砍。size表示在當(dāng)前遍歷層有多少個元素，也就是隊(duì)列中的元素?cái)?shù)庄岖，我們把這些元素一次性遍歷完豁翎，即把當(dāng)前層的所有元素都向外走了一步。
level = 0
while queue 不空：
size = queue.size()
while (size --) {
cur = queue.pop()
for 節(jié)點(diǎn) in cur的所有相鄰節(jié)點(diǎn)：
if 該節(jié)點(diǎn)有效且未被訪問過：
queue.push(該節(jié)點(diǎn))
}
level ++;
上面兩個是通用模板隅忿，在任何題目中都可以用谨垃，是要記住的启搂！
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
# 遞歸
# 時間復(fù)雜度：O(n)硼控，n為節(jié)點(diǎn)數(shù)刘陶，訪問每個節(jié)點(diǎn)恰好一次。
# 空間復(fù)雜度：空間復(fù)雜度：O(h)牢撼，h為樹的高度匙隔。最壞情況下需要空間O(n)，平均情況為O(logn)
# 遞歸1：二叉樹遍歷最易理解和實(shí)現(xiàn)版本
class Solution:
def preorderTraversal(self, root: TreeNode) -> List[int]:
if not root:
return []
# 前序遞歸
return [root.val] + self.preorderTraversal(root.left) + self.preorderTraversal(root.right)
# # 中序遞歸
# return self.inorderTraversal(root.left) + [root.val] + self.inorderTraversal(root.right)
# # 后序遞歸
# return self.postorderTraversal(root.left) + self.postorderTraversal(root.right) + [root.val]
# 遞歸2：通用模板熏版，可以適應(yīng)不同的題目纷责，添加參數(shù)、增加返回條件撼短、修改進(jìn)入遞歸條件再膳、自定義返回值
class Solution:
def preorderTraversal(self, root: TreeNode) -> List[int]:
def dfs(cur):
if not cur:
return
# 前序遞歸
res.append(cur.val)
dfs(cur.left)
dfs(cur.right)
# # 中序遞歸
# dfs(cur.left)
# res.append(cur.val)
# dfs(cur.right)
# # 后序遞歸
# dfs(cur.left)
# dfs(cur.right)
# res.append(cur.val)
res = []
dfs(root)
return res
# 迭代
# 時間復(fù)雜度：O(n)，n為節(jié)點(diǎn)數(shù)曲横，訪問每個節(jié)點(diǎn)恰好一次喂柒。
# 空間復(fù)雜度：O(h)，h為樹的高度禾嫉。取決于樹的結(jié)構(gòu)灾杰，最壞情況存儲整棵樹，即O(n)
# 迭代1：前序遍歷最常用模板（后序同樣可以用）
class Solution:
def preorderTraversal(self, root: TreeNode) -> List[int]:
if not root:
return []
res = []
stack = [root]
# # 前序迭代模板：最常用的二叉樹DFS迭代遍歷模板
while stack:
cur = stack.pop()
res.append(cur.val)
if cur.right:
stack.append(cur.right)
if cur.left:
stack.append(cur.left)
return res
# # 后序迭代熙参，相同模板：將前序迭代進(jìn)棧順序稍作修改艳吠，最后得到的結(jié)果反轉(zhuǎn)
# while stack:
# cur = stack.pop()
# if cur.left:
# stack.append(cur.left)
# if cur.right:
# stack.append(cur.right)
# res.append(cur.val)
# return res[::-1]
# 迭代1：層序遍歷最常用模板
class Solution:
def levelOrder(self, root: TreeNode) -> List[List[int]]:
if not root:
return []
cur, res = [root], []
while cur:
lay, layval = [], []
for node in cur:
layval.append(node.val)
if node.left: lay.append(node.left)
if node.right: lay.append(node.right)
cur = lay
res.append(layval)
return res
# 迭代2：前、中孽椰、后序遍歷通用模板（只需一個棧的空間）
class Solution:
def inorderTraversal(self, root: TreeNode) -> List[int]:
res = []
stack = []
cur = root
# 中序昭娩，模板：先用指針找到每顆子樹的最左下角，然后進(jìn)行進(jìn)出棧操作
while stack or cur:
while cur:
stack.append(cur)
cur = cur.left
cur = stack.pop()
res.append(cur.val)
cur = cur.right
return res
# # 前序黍匾，相同模板
# while stack or cur:
# while cur:
# res.append(cur.val)
# stack.append(cur)
# cur = cur.left
# cur = stack.pop()
# cur = cur.right
# return res
# # 后序栏渺，相同模板
# while stack or cur:
# while cur:
# res.append(cur.val)
# stack.append(cur)
# cur = cur.right
# cur = stack.pop()
# cur = cur.left
# return res[::-1]
# 迭代3：標(biāo)記法迭代（需要雙倍的空間來存儲訪問狀態(tài)）：
# 前、中膀捷、后迈嘹、層序通用模板，只需改變進(jìn)棧順序或即可實(shí)現(xiàn)前后中序遍歷全庸，
# 而層序遍歷則使用隊(duì)列先進(jìn)先出秀仲。0表示當(dāng)前未訪問，1表示已訪問壶笼。
class Solution:
def preorderTraversal(self, root: TreeNode) -> List[int]:
res = []
stack = [(0, root)]
while stack:
flag, cur = stack.pop()
if not cur: continue
if flag == 0:
# 前序神僵，標(biāo)記法
stack.append((0, cur.right))
stack.append((0, cur.left))
stack.append((1, cur))
# # 后序，標(biāo)記法
# stack.append((1, cur))
# stack.append((0, cur.right))
# stack.append((0, cur.left))
# # 中序覆劈，標(biāo)記法
# stack.append((0, cur.right))
# stack.append((1, cur))
# stack.append((0, cur.left))
else:
res.append(cur.val)
return res
# # 層序保礼，標(biāo)記法
# res = []
# queue = [(0, root)]
# while queue:
# flag, cur = queue.pop(0) # 注意是隊(duì)列沛励，先進(jìn)先出
# if not cur: continue
# if flag == 0:
# 層序遍歷這三個的順序無所謂，因?yàn)槭顷?duì)列炮障，只彈出隊(duì)首元素
# queue.append((1, cur))
# queue.append((0, cur.left))
# queue.append((0, cur.right))
# else:
# res.append(cur.val)
# return res
# 莫里斯遍歷
# 時間復(fù)雜度：O(n)目派，n為節(jié)點(diǎn)數(shù)，看似超過O(n)胁赢，有的節(jié)點(diǎn)可能要訪問兩次企蹭，實(shí)際分析還是O(n)，具體參考大佬博客的分析智末。
# 空間復(fù)雜度：O(1)谅摄，如果在遍歷過程中就輸出節(jié)點(diǎn)值，則只需常數(shù)空間就能得到中序遍歷結(jié)果系馆，空間只需兩個指針送漠。
# 如果將結(jié)果儲存最后輸出，則空間復(fù)雜度還是O(n)由蘑。
# PS：莫里斯遍歷實(shí)際上是在原有二叉樹的結(jié)構(gòu)基礎(chǔ)上闽寡，構(gòu)造了線索二叉樹，
# 線索二叉樹定義為：原本為空的右子節(jié)點(diǎn)指向了中序遍歷順序之后的那個節(jié)點(diǎn)纵穿，把所有原本為空的左子節(jié)點(diǎn)都指向了中序遍歷之前的那個節(jié)點(diǎn)
# emmmm下隧，好像大學(xué)教材學(xué)過，還考過
# 此處只給出中序遍歷谓媒，前序遍歷只需修改輸出順序即可
# 而后序遍歷淆院，由于遍歷是從根開始的，而線索二叉樹是將為空的左右子節(jié)點(diǎn)連接到相應(yīng)的順序上句惯，使其能夠按照相應(yīng)準(zhǔn)則輸出
# 但是后序遍歷的根節(jié)點(diǎn)卻已經(jīng)沒有額外的空間來標(biāo)記自己下一個應(yīng)該訪問的節(jié)點(diǎn)土辩，
# 所以這里需要建立一個臨時節(jié)點(diǎn)dump，令其左孩子是root抢野。并且還需要一個子過程拷淘，就是倒序輸出某兩個節(jié)點(diǎn)之間路徑上的各個節(jié)點(diǎn)。
# 具體參考大佬博客
# 莫里斯遍歷指孤，借助線索二叉樹中序遍歷（附前序遍歷）
class Solution:
def inorderTraversal(self, root: TreeNode) -> List[int]:
res = []
# cur = pre = TreeNode(None)
cur = root
while cur:
if not cur.left:
res.append(cur.val)
# print(cur.val)
cur = cur.right
else:
pre = cur.left
while pre.right and pre.right != cur:
pre = pre.right
if not pre.right:
# print(cur.val) 這里是前序遍歷的代碼启涯，前序與中序的唯一差別，只是輸出順序不同
pre.right = cur
cur = cur.left
else:
pre.right = None
res.append(cur.val)
# print(cur.val)
cur = cur.right
return res
# N叉樹遍歷
# 時間復(fù)雜度：時間復(fù)雜度：O(M)恃轩，其中 M 是 N 叉樹中的節(jié)點(diǎn)個數(shù)结洼。每個節(jié)點(diǎn)只會入棧和出棧各一次。
# 空間復(fù)雜度：O(M)叉跛。在最壞的情況下松忍，這棵 N 叉樹只有 2 層，所有第 2 層的節(jié)點(diǎn)都是根節(jié)點(diǎn)的孩子筷厘。
# 將根節(jié)點(diǎn)推出棧后鸣峭，需要將這些節(jié)點(diǎn)都放入棧宏所，共有 M?1個節(jié)點(diǎn)，因此棧的大小為 O(M)摊溶。
"""
# Definition for a Node.
class Node:
def __init__(self, val=None, children=None):
self.val = val
self.children = children
"""
# N叉樹簡潔遞歸
class Solution:
def preorder(self, root: 'Node') -> List[int]:
if not root: return []
res = [root.val]
for node in root.children:
res.extend(self.preorder(node))
return res
# N叉樹通用遞歸模板
class Solution:
def preorder(self, root: 'Node') -> List[int]:
res = []
def helper(root):
if not root:
return
res.append(root.val)
for child in root.children:
helper(child)
helper(root)
return res
# N叉樹迭代方法
class Solution:
def preorder(self, root: 'Node') -> List[int]:
if not root:
return []
s = [root]
# s.append(root)
res = []
while s:
node = s.pop()
res.append(node.val)
# for child in node.children[::-1]:
# s.append(child)
s.extend(node.children[::-1])
return res
