图解LeetCode——102. 二叉树的层序遍历

原创

爪哇缪斯

修改于 2023-07-13 22:53:00

1750

修改于 2023-07-13 22:53:00

文章被收录于专栏：爪哇缪斯爪哇缪斯

一、题目

给你二叉树的根节点 root ，返回其节点值的 层序遍历 。（即逐层地，从左到右访问所有节点）。

二、示例

2.1> 示例 1：

【输入】root = [3,9,20,null,null,15,7] 【输出】[[3],[9,20],[15,7]]

2.2> 示例 2：

【输入】root = [1] 【输出】[[1]]

2.3> 示例 3：

【输入】root = [] 【输出】[]

提示：

树中节点数目在范围 [0, 2000] 内
-1000 <= Node.val <= 1000

三、解题思路

3.1> 思路1：广度优先遍历

根据题目要求，我们要实现二叉树的从上到下，从左向右的遍历输出。那么每一层我们将其保存到一个List中，然后所有二叉树节点都遍历完毕后，就输出List<List<Integer>> result即可。

那么我们可以首先采用广度优先遍历方式，去输出每个节点，处理方式就是首先我们来创建一个队列deque，用于暂存遍历的节点。操作伪代码如下所示：

int?num；?//?第N层节点个数
while(deque不为空）{
???num?=?deque中存储的元素个数；
?????创建新的list；
???for?(int?i?=?0;?i?<?num;?i++)?{
?????????从deque中获得Node节点；
?????????将Node节点的val值保存到list中；
?????????将Node的左子树leftNode存放到deque中；
?????????将Node的右子树rightNode存放到deque中；
???}
}

其中，关键的点就是通过deque来暂存节点，以及每次从deque中获取num个节点元素。因为deque中有可能存入的是两个层中的Node节点，那么就无法区分哪些是一层的了。为了便于理解，下面我们以输入root = [3,9,20,null,null,15,7]为例，看一下具体的处理过程。

3.2> 思路2：深度优先遍历

除了广度优先，我们也可以采用深度优先算法来进行解题，这里面我们可以通过借助递归的方式，将level层级作为方法入参，然后利用list.get(level)的方式获得这个层级的节点值集合。操作步骤如下所示：

【步骤1】遍历某level层节点，如果list中没有创建该层集合，则创建，然后将节点的val值保存进去。如果已创建，则通过list.get(level)的方式获取该层集合。【步骤2】获取leftNode传入递归方法中，并且level入参值加1；【步骤3】获取rightNode传入递归方法中，并且level入参值加1；

以上就是深度优先遍历的解题思路，为了便于理解，下面我们以输入root = [3,9,20,null,null,15,7]为例，看一下具体的处理过程。

四、代码实现

4.1> 实现1：广度优先遍历

class?Solution?{
????public?List<List<Integer>>?levelOrder(TreeNode?root)?{
????????List<List<Integer>>?result?=?new?ArrayList();
????????if?(root?==?null)?return?result;
????????Deque<TreeNode>?deque?=?new?ArrayDeque();
????????deque.addLast(root);
????????int?num;
????????while(!deque.isEmpty())?{
????????????num?=?deque.size();
????????????LinkedList<Integer>?item?=?new?LinkedList<>();
????????????for?(int?i?=?0;?i?<?num;?i++)?{
????????????????TreeNode?node?=?deque.removeFirst();
????????????????item.addLast(node.val);
????????????????if?(node.left?!=?null)?deque.addLast(node.left);
????????????????if?(node.right?!=?null)?deque.addLast(node.right);
????????????}
????????????result.add(item);
????????}
????????return?result;
????}
}

4.2> 实现2：深度优先遍历

class?Solution?{
????List<List<Integer>>?result?=?new?ArrayList();
????public?List<List<Integer>>?levelOrder(TreeNode?root)?{
????????dfs(root,?0);
????????return?result;
????}

????public?void?dfs(TreeNode?node,?int?level)?{
????????if?(node?==?null)?return;
????????if?(result.size()?==?level)?result.add(new?ArrayList());
????????result.get(level).add(node.val);
????????dfs(node.left,?level?+?1);
????????dfs(node.right,?level?+?1);
????}
}