題目
給你二叉樹(shù)的根節(jié)點(diǎn) root 什黑，返回其節(jié)點(diǎn)值的 層序遍歷 崎淳。即逐層地，從左到右訪問(wèn)所有節(jié)點(diǎn)愕把。
例：
輸入：root = [3,9,20,null,null,15,7]
輸出：[[3],[9,20],[15,7]]
方法：遞歸
遞歸部分的實(shí)現(xiàn)：
- 首先拣凹，判斷此時(shí)的節(jié)點(diǎn)是否存在，若不存在恨豁，則直接返回空
- （因?yàn)橛涗浗Y(jié)果的列表的記錄方式為列表的不斷嵌套嚣镜，同一層的所有結(jié)點(diǎn)的值放在同一個(gè)列表中；同時(shí)橘蜜，又因?yàn)槲覀儗⒍鏄?shù)的深度從零開(kāi)始菊匿，所以當(dāng)進(jìn)入一個(gè)新的深度時(shí)，此時(shí)記錄結(jié)果的列表的長(zhǎng)度是等于該層的深度的扮匠。）判斷此時(shí)記錄結(jié)果的列表長(zhǎng)度是否等于此時(shí)需要遍歷的層的深度捧请，若相等，則表示此時(shí)為第一次遍歷該層棒搜，所以在原始列表中嵌套新的列表
- 添加中間節(jié)點(diǎn)至此時(shí)深度的列表
- 若該中間節(jié)點(diǎn)存在左孩子，則使該左孩子作為新的中間節(jié)點(diǎn)開(kāi)始新一輪遞歸
- 若該中間節(jié)點(diǎn)存在右孩子活箕，則使該右孩子作為新的中間節(jié)點(diǎn)開(kāi)始新一輪遞歸
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution(object):
def levelOrder(self, root):
result = []
def DFS(root, depth):
if not root:
return
if len(result) == depth:
result.append([])
result[depth].append(root.val)
if root.left:
DFS(root.left, depth + 1)
if root.right:
DFS(root.right, depth + 1)
DFS(root, 0)
return result
相關(guān)知識(shí)
-
深度優(yōu)先遍歷 Depth First Search （DFS）：
對(duì)每一個(gè)可能的分支路徑深入到不能再深入為止力麸，而且每個(gè)節(jié)點(diǎn)只能訪問(wèn)一次
