前言

• 科研不順啊......又不想搞了，隨便弄弄吧，多花點時間刷題，今天開啟二叉樹！

94. 二叉樹的中序遍歷 - 力扣（LeetCode）

• 遞歸

  • # 最簡單遞歸
    class Solution:def inorderTraversal(self, root: TreeNode) -> List[int]:if not root:return []return self.inorderTraversal(root.left) + [root.val] + self.inorderTraversal(root.right)# 通用模板        
    class Solution:def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:res = []  # 收集結果def dfs(root):if not root:  # 訪問到空結點直接返回returndfs(root.left)        # 左res.append(root.val)  # 中dfs(root.right)       # 右dfs(root)return res

• 迭代

  • 圖和代碼參考王尼瑪題解
  • 

  • class Solution:def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:res = []stack = []while stack or root:# 不斷往左子樹方向走，每走一次就將當前節點保存到棧中# 這是模擬遞歸的調用if root:stack.append(root)root = root.left# 當前節點為空，說明左邊走到頭了，從棧中彈出節點并保存# 然后轉向右邊節點，繼續上面整個過程else:temp = stack.pop()res.append(temp.val)root = temp.rightreturn res

• ?Morris遍歷

  • 過程看官解的動圖
  • cur無左孩子，說明到最左端：
    • 加入結果，cur右移
  • cur有左孩子，說明有前驅，找前驅
    • 前驅無右孩：生成鏈接、cur左移
    • 前驅有右孩：斷開連接，記錄cur結果，cur右移

  • class Solution:def inorderTraversal(self, root: TreeNode) -> List[int]:res = []  # 用于存儲中序遍歷結果的列表cur, prev = root, None  # 初始化當前節點cur和前驅節點prevwhile cur:  # 當前節點cur不為空時循環執行if not cur.left:  # 左子樹為空（到最左端）res.append(cur.val)  # 將當前節點cur的值加入結果列表cur = cur.right  # 將當前節點指向右子樹else:prev = cur.left  # 找到當前節點cur的左子樹的最右節點（前驅）while prev.right and prev.right != cur:prev = prev.rightif not prev.right:  # 如果前驅節點的右孩子為空（添加連接）prev.right = cur  # 將前驅節點的右孩子指向當前節點cur = cur.left  # 將當前節點移動到左子樹else:prev.right = None  # 恢復最右節點右孩子為空res.append(cur.val)  # 將當前節點cur的值加入結果列表cur = cur.right  # 將當前節點移動到右子樹return res  # 返回中序遍歷結果

• ?標記迭代

  • class Solution:def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:res = []stack = [(0, root)]  # 0表示當前未訪問，1表示已訪問while stack:flag, cur = stack.pop()if not cur: continueif flag == 0:stack.append((0, cur.right))  # 右stack.append((1, cur))        # 中stack.append((0, cur.left))   # 左else:res.append(cur.val)return res
    

二叉樹所有遍歷模板總結

144. 二叉樹的前序遍歷 - 力扣（LeetCode）

145. 二叉樹的后序遍歷 - 力扣（LeetCode）

102. 二叉樹的層序遍歷 - 力扣（LeetCode）

589. N 叉樹的前序遍歷 - 力扣（LeetCode）

后言

• 今天把以上幾個二叉樹遍歷的題目模板刷熟！這樣后面的題才能信手拈來~