劍指 Offer 32 - II. 從上到下打印二叉樹(shù) II
從上到下按層打印二叉樹(shù)，同一層的節(jié)點(diǎn)按從左到右的順序打印，每一層打印到一行。
例如:
給定二叉樹(shù): [3,9,20,null,null,15,7],
? ? 3
? ?/ \
? 9? 20
? ? /? \
? ?15? ?7
返回其層次遍歷結(jié)果：
[
? [3],
? [9,20],
? [15,7]
]
提示：
節(jié)點(diǎn)總數(shù) <= 1000
題目解析
I. 按層打印：題目要求的二叉樹(shù)的 從上至下 打印（即按層打印），又稱(chēng)為二叉樹(shù)的 廣度優(yōu)先搜索（BFS）。BFS 通常借助 隊(duì)列 的先入先出特性來(lái)實(shí)現(xiàn)。
II. 每層打印到一行：將本層全部節(jié)點(diǎn)打印到一行，并將下一層全部節(jié)點(diǎn)加入隊(duì)列，以此類(lèi)推，即可分為多行打印。
題目解答
代碼展示
方法一：廣度優(yōu)先搜索?層次遍歷法（遞歸）
# Definition for a binary tree node.# class TreeNode:# def __init__(self, x):# self.val = x# self.left = None# self.right = Noneclass?Solution:???????def?levelOrder(self,?root:?TreeNode)?->?List[List[int]]:'''方法一：廣度優(yōu)先搜索 層次遍歷法（遞歸）'''# step 1：判空res = []if not root:return res# step 2：廣度優(yōu)先搜索level = 0res=self.bfs(root,0,res)return res# 方法：廣度優(yōu)先搜索def bfs(self,root,level,res):# step 1：終止條件判斷if level==len(res):res.append([])# step 2：先根->左->右res[level].append(root.val)if root.left:self.bfs(root.left,level+1,res)if root.right:self.bfs(root.right,level+1,res)????????return?res
????
方法二：隊(duì)列迭代?(非遞歸)
# Definition for a binary tree node.# class TreeNode:# def __init__(self, x):# self.val = x# self.left = None# self.right = Noneclass Solution:def levelOrder(self, root: TreeNode) -> List[List[int]]:'''方法二：隊(duì)列迭代 (非遞歸)'''res = []if not root:return resqueue = collections.deque()queue.append(root)while queue:level = []for _ in range(len(queue)):node = queue.popleft()level.append(node.val)if node.left:queue.append(node.left)if node.right:queue.append(node.right)res.append(level)????????return?res
復(fù)雜度計(jì)算
?時(shí)間復(fù)雜度：O(N)，其中 N 是二叉樹(shù)的節(jié)點(diǎn)數(shù)。二叉樹(shù)的所有節(jié)點(diǎn)有且只會(huì)被訪問(wèn)一次，因此時(shí)間復(fù)雜度為 O(N)。
-空間復(fù)雜度：O(N)，當(dāng)樹(shù)為平衡二叉樹(shù)時(shí)，最多有N/2個(gè)樹(shù)節(jié)點(diǎn)入隊(duì)，使用 O(N)?大小的額外空間
運(yùn)行結(jié)果
方法一：廣度優(yōu)先搜索?層次遍歷法（遞歸）
方法二：隊(duì)列迭代?(非遞歸)
評(píng)論
圖片
表情