class TreeNode: def __init__(self, x): self.val = x self.left = None self.right = Nonefrom typing import Listclass Solution: # 迭代的想法 def levelOrderBot ...
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
from typing import List
class Solution:
# 迭代的想法
def levelOrderBottom1(self, root: TreeNode) -> List[List[int]]:
# 導入雙向隊列類
from collections import deque
# 如果鏈表為空，返回空列表
if not root:return []
# 定義一個雙向隊列
queue = deque()
# 在隊列左邊添加根節點
queue.appendleft(root)
# 定義一個空列表
last_list = []
# 進行迴圈
while queue:
# 定義一個當前列表，用來存放每一層節點的值
now_list = []
# 當前有幾個節點就迴圈幾次。
for _ in range(len(queue)):
# 彈出一個值，
value = queue.pop()
# 把彈出的值添加進入當前列表
now_list.append(value.val)
# 判斷此節點有沒有左右兒子，如果有的話，就將他們從隊列左邊加入
# 註意，想一下為什麼hi從左邊加入
if value.left:
queue.appendleft(value.left)
if value.right:
queue.appendleft(value.right)
# 這裡也要講當前列表插入最終列表的最左邊。
last_list.insert(0,now_list)
return last_list
# 遞歸的想法
def levelOrderBottom2(self, root: TreeNode) -> List[List[int]]:
# 首先定義一個列表，用來存放最終的數據
res = []
# 定義遞歸函數，兩個參數，一個是節點，一個是層數
def dfs(root,depth):
# 如果當前節點為空，函數無需向下進行
if not root:return
# 當函數走到鏈表每一層最左邊的節點的時候，
# 就插入一個空列表，
if depth == len(res):
res.insert(0,[])
res[-(depth + 1)].append(root.val)
dfs(root.left,depth + 1)
dfs(root.right,depth + 1)
dfs(root,0)
return res
