思想

二叉樹的核心思想是分治和遞歸，特點是遍歷方式。
解題方式常見兩類思路：

1. 遍歷一遍二叉樹尋找答案；
2. 通過分治分解問題尋求答案；

遍歷分為前中后序，本質上是遍歷二叉樹過程中處理每個節(jié)點的三個特殊時間點：

1. 前序是在剛剛進入二叉樹節(jié)點時執(zhí)行；
2. 后序是在將要離開二叉樹節(jié)點時執(zhí)行；
3. 中序是左子樹遍歷完進入右子樹前執(zhí)行；

# 前序
     1 node
    /      \
 2 left   3 right
中左右
 
# 中序
     2 node
    /      \
 1 left    3 right
左中右
 
# 后序
     3 node
    /      \
 1 left    2 right     
左右中       

多叉樹只有前后序列遍歷，因為只有二叉樹有唯一一次中間節(jié)點的遍歷

題目的關鍵就是找到遍歷過程中的位置，插入對應代碼邏輯實現(xiàn)場景的目的。

實例

二叉樹的層序遍歷 leetcode 102

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

輸入：
root: TreeNode，二叉樹的根節(jié)點

輸出：
List[List[int]]，返回節(jié)點值的層序遍歷。

舉例：
給定二叉樹 [3,9,20,null,null,15,7]
總共 3 層，分層遍歷返回，[[3], [9,20], [15,7]]

   3
  / \
 9  20
    / \
   15   7

二叉樹的數(shù)據(jù)存儲可以使用鏈表，也可以使用數(shù)組，往往數(shù)組更容易表達，根節(jié)點從 index=1 處開始存儲，浪費 index=0 的位置
left_child = 2 * parent
right_child = 2 * parent + 1
parent = child // 2

遍歷解

層序遍歷在每一層是從左到右的，解題關鍵是識別當前節(jié)點在哪一層，這決定了將當前的節(jié)點值寫入返回數(shù)組的哪一級；
另一是實現(xiàn)從左到右的遍歷，這個過程符合隊列的數(shù)據(jù)結構。
使用隊列來存儲待遍歷的節(jié)點，上例，使用 result = [] 記錄遍歷的結果：

• 首先從 [(0, TreeNode(3))] 開始，高度 0 == len(result)，此時標志著新的一層開始，建立當層的列表放入 result，result = [[3]]，同時高度設置為
  1。再將左右子樹的節(jié)點放入待遍歷列表，[(1, TreeNode(20), (1, TreeNode(9)))]；
• 繼續(xù)從待遍歷列表取出隊列尾部元素 (1, TreeNode(9))，高度 1 == len(result)，此時標志著新的一層開始，建立當層的列表放入 result，result = [[3], [9]]，同時高度設置為
  2，沒有左右子樹節(jié)點；
• 繼續(xù)從待遍歷列表取出隊列尾部元素 (1, TreeNode(20))，高度 1 < len(result)，標志當前層的繼續(xù)遍歷，在對應層高 1 的下標數(shù)組增加當前節(jié)點值，result = [[3], [9,20]]
  。再將左右子樹的節(jié)點放入待遍歷列表，[(2, TreeNode(7)), (2, TreeNode(15))]；
• 繼續(xù)從待遍歷列表取出隊列尾部元素 (2, TreeNode(15))，高度 2 == len(result)，此時標志著新的一層開始，建立當層的列表放入 result，result = [[3], [9,20], [15]]
  ，同時高度設置為 3，沒有左右子樹節(jié)點；
• 繼續(xù)從待遍歷列表取出隊列尾部元素 (2, TreeNode(7))，高度 2 < len(result)，標志當前層的繼續(xù)遍歷，在對應層高 1 的下標數(shù)組增加當前節(jié)點值，result = [[3], [9,20], [15,7]]
  ，沒有左右子樹節(jié)點；

分治解

分治需要抽象每個節(jié)點的情況，在前序位置要判斷返回結果是否需要增加一個新的 list，具體參看下例代碼，基礎思路和分析與遍歷是一致的。

編碼

from typing import Optional


class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


def binary_tree_level_order_traversal(root: Optional[TreeNode]) -> List[List[int]]:
    # 申請一塊內(nèi)存存儲待遍歷的節(jié)點和深度
    node_queue = []
    result = []
    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(result):
            # 下標從 0 開始，如果當前節(jié)點高度大于等于遍歷內(nèi)存的長度，說明進入了新的一層，創(chuàng)建一個新的 list 放入 node_queue
            result.append([cur_node.val])
            # 新的一層全局的高度增加
            height += 1
        else:
            # 當前層遍歷，將節(jié)點值放入當前層的 list
            result[cur_height].append(cur_node.val)
        if cur_node.left:
            node_queue.insert(0, (height, cur_node.left))
        if cur_node.right:
            node_queue.insert(0, (height, cur_node.right))
    return result


def binary_tree_level_order_traversal_recursive(root: Optional[TreeNode]) -> List[List[int]]:
    result = []

    def traverse(root: Optional[TreeNode], height: int):
        # base 條件，根節(jié)點為空無需處理
        if root is None:
            return
        # 前序位置，首次進入，排查高度
        if len(result) <= height:
            result.append([])
        result[height].append(root.val)
        traverse(root.left, height + 1)
        traverse(root.right, height + 1)

    # 邊界條件保護
    if root is None:
        return result
    traverse(root, 0)
    return result

相關

二叉樹 0
二叉樹 1
二叉樹 2
二叉樹 3
二叉樹 4
二叉樹 5
二叉樹 6