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 = https://www.cnblogs.com/cong12586/p/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
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/136656.html
標籤：Python