LeetCode 双刀流：102. Binary Tree Level Order Traversal

102. Binary Tree Level Order Traversal

今天一样延续着「二元树（Binary Tree）」的题目，其实树相关的议题可以算是面试时的热门考题，不同的情境可以玩转资料结构与演算法两种方向。常见的遍历方法有依据 Root 被找到的先後做排序的「前序」、「中序」跟「後序」，但一题考的是以阶层（深度）为顺序的「Level Order Traversal」。

先看一下题目描述

Given the root of a binary tree, return the level order traversal of its nodes' values. (i.e., from left to right, level by level).

再搭配范例理解题目

• Example 1:

Input: root = [3,9,20,null,null,15,7]
Output: [[3],[9,20],[15,7]]

阶层（Level）在树当中代表的是深度，从最上层的 Root 开始依序往下层增加。根据不同的定义可能会从 Level = 0 或 Level = 1 开始计数，但这一题不影响。而这个要求用阶层为单位，将同一层的点放在同一个容器、依序将不同层的容器再放在一个大的容器内回传。

开始实作

在理解完题目与条件之後，那我们下一步就开始「#初探直觉解」并且一起尝试「#刻意优化」的过程：

方法 ①：自定义储存格式

这个题目比较麻烦的地方在於要如何找出每一个点分别在哪一层当中，因此第一个想法是可以利用 map 自定义储存格式，将点与所在阶层记录下来：

waitlist = [ 
    { 'level': 0, 'node': root}
]

首先，将每一个纪录中的根据阶层储存到最终的结果中：

while len(waitlist) > 0:
    cur = waitlist.pop()
    node = cur['node']
    
    res[cur['level']].append(node.val)

同时也需要将每一个点下一层的左右两点记录下来：

while len(waitlist) > 0:
    cur = waitlist.pop()
    node = cur['node']
    waitlist.append({'level': cur['level']+1, 'node':node.right});
    waitlist.append({'level': cur['level']+1, 'node':node.left});

用 Python 实作一次

class Solution:
    def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        if not root:  return []

        res = {};
        waitlist = [ { 'level': 0, 'node': root} ]

        while len(waitlist) > 0:
            cur = waitlist.pop()
            node = cur['node']
            
            res.setdefault(cur['level'], [])
            res[cur['level']].append(node.val)

            if node.right:
                waitlist.append({'level':cur['level']+1, 'node':node.right});
            if node.left:
                waitlist.append({'level':cur['level']+1, 'node':node.left});

        return [res[i] for i in res]

也可以用 JavaScript 复刻一次

var levelOrder = function(root) {
    if (!root)  return [];

    var res = {};
    var waitlist = [ { level:0, node:root} ];

    while(waitlist.length > 0){
        var cur = waitlist.pop();
        var node = cur.node;
        
        if(!res[cur.level]) res[cur.level] = [];
        res[cur.level].push(node.val);
        
        if(node.right) waitlist.push({level:cur.level+1, node:node.right});
        if(node.left) waitlist.push({level:cur.level+1, node:node.left});
    }
    
    var result = [];
    for(var i in res){
        result.push(d[i]);
    }

    return result;
};

方法 ②：用 Stack 暂存资料

第二种方法可以利用 Stack 的特性来记忆不同阶层的资料，而不用自订义的格式来记录。这种方法将 Stack 作为所有需要跑过一轮的点，然後再利用 currents 存放该层的点、childs 存放下一层的点。每跑过一轮时，将 currents 合并回结果，将 childs 写入 stack 作为下一轮需要考虑的点。

用 Python 实作一次

class Solution:
    def levelOrder(self, root: TreeNode) -> List[List[int]]:
        if not root: return []
        res, stack = [], [[root]]

        while stack:
            nodes = stack.pop()
            currents = []
            childs = []
            for node in nodes:
                currents.append(node.val)
                if node.left: childs.append(node.left)
                if node.right: childs.append(node.right)
            
            res.append(currents)
            if childs: stack.append(childs)
                
        return res

也可以用 JavaScript 复刻一次

const levelOrder = function(root) {
    if (!root)  return [];
    let res = [], stack = [[root]];
    
    while (stack.length > 0) {
        nodes = stack.pop()
        currents = []
        childs = []
        for(let node of nodes){
            currents.push(node.val)
            if(node.left) childs.push(node.left)
            if(node.right) childs.push(node.right)
        }
        res.push(currents)
        if(childs.length > 0) stack.push(childs)
    }
    return res;
};

方法 ③：用 Queue 暂存资料

在 Stack 中方法中需要利用两层的 [[...]] 用来储存上下层的资料，才能区分先後的关系。但如果我们改用 Queue 的结构，因为其先进先出（FIFO）的特性，只需要改成 [...] 一层来存放即可：

用 Python 实作一次

class Solution:
    def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        if not root:  return []
        res, queue = [], [root]

        while queue:
            levelQueue = []
            for _ in range(len(queue)):
                node = queue.pop(0)
                levelQueue.append(node.val)
                if node.left: queue.append(node.left)
                if node.right: queue.append(node.right)   
            res.append(levelQueue)
        
        return res

也可以用 JavaScript 复刻一次

const levelOrder = function(root) {
    if (!root)  return [];
    let res = [], queue = [root];
    
    while (queue.length > 0) {
        let levelQueue = [];
        let length = queue.length;
        for(let i = 0; i < length; i++){
            const node = queue.shift(); 
            levelQueue.push(node.val)
            if(node.left !== null) queue.push(node.left);
            if(node.right !== null) queue.push(node.right);
        }
        res.push(levelQueue)
    }
    return res;
};

反思沉淀

遍历是树（Tree）特性的一种延伸操作，不同於线性的搜寻，因为每一个节点可能会有左/右分支，因此有不同的先後顺序找法。这个题目可以搭配「自定义的格式」或直接利用「Stack」与「Queue」之类的抽象资料结构特性来保存资料间的顺序来实现题目要求。

举一反三看看相似题

最後可以从题目提供的相似题看一下有哪些类似的题目，适合作为你下一个尝试的练习：

• 107. Binary Tree Level Order Traversal II
• 111. Minimum Depth of Binary Tree
• 637. Average of Levels in Binary Tree
• 429. N-ary Tree Level Order Traversal

嗨，大家好！我是维元，一名擅长网站开发与资料科学的双栖工程师，斜杠於程序社群【JSDC】核心成员及【资料科学家的工作日常】粉专经营。目前在 ALPHACamp 担任资料工程师，同时也在中华电信、工研院与多所学校等单位持续开课。拥有多次大型技术会议讲者与竞赛获奖经验，持续在不同的平台发表对 #资料科学、 #网页开发 或 #软件职涯 相关的分享，邀请你加入 订阅 接收最新资讯。