思想
二叉樹的核心思想是分治和遞歸，特點(diǎn)是遍歷方式裕偿。
解題方式常見兩類思路：
- 遍歷一遍二叉樹尋找答案尊剔；
- 通過分治分解問題尋求答案爪幻；
遍歷分為前中后序，本質(zhì)上是遍歷二叉樹過程中處理每個節(jié)點(diǎn)的三個特殊時間點(diǎn)：
- 前序是在剛剛進(jìn)入二叉樹節(jié)點(diǎn)時執(zhí)行须误；
- 后序是在將要離開二叉樹節(jié)點(diǎn)時執(zhí)行挨稿；
- 中序是左子樹遍歷完進(jìn)入右子樹前執(zhí)行；
# 前序
1 node
/ \
2 left 3 right
中左右
# 中序
2 node
/ \
1 left 3 right
左中右
# 后序
3 node
/ \
1 left 2 right
左右中
多叉樹只有前后序列遍歷京痢，因?yàn)橹挥卸鏄溆形ㄒ灰淮沃虚g節(jié)點(diǎn)的遍歷
題目的關(guān)鍵就是找到遍歷過程中的位置奶甘，插入對應(yīng)代碼邏輯實(shí)現(xiàn)場景的目的。
實(shí)例
在每個樹行中尋找最大值 leetcode 515
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
輸入：
root: TreeNode祭椰，二叉樹的根節(jié)點(diǎn)
輸出：
List[int]臭家，返回每層中的最大值。
舉例：
給定二叉樹 [1,3,2,5,3,null,9]
總共 3 層方淤，分層遍歷記錄最大值钉赁，[1, 3, 9]
1
/ \
3 2
/ \ \
5 3 9
二叉樹的數(shù)據(jù)存儲可以使用鏈表，也可以使用數(shù)組携茂，往往數(shù)組更容易表達(dá)你踩，根節(jié)點(diǎn)從 index=1 處開始存儲，浪費(fèi) index=0 的位置
left_child = 2 * parent
right_child = 2 * parent + 1
parent = child // 2
遍歷解
層序遍歷在每一層是從左到右的讳苦，解題關(guān)鍵是識別當(dāng)前節(jié)點(diǎn)在哪一層带膜，這決定了將當(dāng)前的節(jié)點(diǎn)值寫入返回?cái)?shù)組的哪一級；
另一是實(shí)現(xiàn)從左到右的遍歷医吊，這個過程符合隊(duì)列的數(shù)據(jù)結(jié)構(gòu)钱慢。
使用隊(duì)列來存儲待遍歷的節(jié)點(diǎn)逮京，上例卿堂，使用 result = [] 記錄遍歷的結(jié)果：
- 首先從 [(0, TreeNode(1))] 開始，高度 0 == len(result)懒棉，此時標(biāo)志著新的一層開始草描，建立當(dāng)層的列表放入 result，result = [1]策严，同時高度設(shè)置為
1穗慕。再將左右子樹的節(jié)點(diǎn)放入待遍歷列表，[(1, TreeNode(2), (1, TreeNode(3)))]妻导； - 繼續(xù)從待遍歷列表取出隊(duì)列尾部元素 (1, TreeNode(3))逛绵，高度 1 == len(result)怀各，此時標(biāo)志著新的一層開始，建立當(dāng)層的列表放入 result术浪，result = [1, 3]瓢对，同時高度設(shè)置為
2，再將左右子樹的節(jié)點(diǎn)放入待遍歷列表胰苏，[(2, TreeNode(3)), (2, TreeNode(5)),(1, TreeNode(3)))]硕蛹； - 繼續(xù)從待遍歷列表取出隊(duì)列尾部元素 (1, TreeNode(3))，高度 1 < len(result)硕并，標(biāo)志當(dāng)前層的繼續(xù)遍歷法焰，在對應(yīng)層高 1 的下標(biāo)找最大值，result = [1倔毙，3]
埃仪。再將左右子樹的節(jié)點(diǎn)放入待遍歷列表，[(2, TreeNode(9)), (2, TreeNode(3)), (2, TreeNode(5))]普监； - 繼續(xù)從待遍歷列表取出隊(duì)列尾部元素 (2, TreeNode(5))贵试，高度 2 == len(result)，此時標(biāo)志著新的一層開始凯正，建立當(dāng)層的列表放入 result毙玻，result = [1,3,5]
，同時高度設(shè)置為 3廊散，沒有左右子樹節(jié)點(diǎn)桑滩； - 繼續(xù)從待遍歷列表取出隊(duì)列尾部元素 (2, TreeNode(3))，高度 2 < len(result)允睹，標(biāo)志當(dāng)前層的繼續(xù)遍歷运准，在對應(yīng)層高 2 的下標(biāo)找最大值，result = [1,3,5]
缭受，沒有左右子樹節(jié)點(diǎn)胁澳； - 繼續(xù)從待遍歷列表取出隊(duì)列尾部元素 (2, TreeNode(9))，高度 2 < len(result)米者，標(biāo)志當(dāng)前層的繼續(xù)遍歷韭畸，在對應(yīng)層高 2 的下標(biāo)找最大值，result = [1,3,9]
蔓搞，沒有左右子樹節(jié)點(diǎn)胰丁；
編碼
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_largest_value_in_each_tree_row(root: Optional[TreeNode]) -> List[int]:
# 初始化
level_max = []
node_queue = []
height = 0
if root is not None:
node_queue.insert(0, (height, root))
# 層序遍歷
while node_queue:
cur_height, cur_node = node_queue.pop()
if cur_height == len(level_max):
# 新的一層創(chuàng)建一個新的對象
level_max.append(cur_node.val)
height += 1
else:
# 遍歷已有層選取歷史上最大值
level_max[cur_height] = max(level_max[cur_height], cur_node.val)
if cur_node.left is not None:
node_queue.insert(0, (height, cur_node.left))
if cur_node.right is not None:
node_queue.insert(0, (height, cur_node.right))
return level_max
