二叉树的层序遍历（广度优先搜索）

层序遍历（Level Order Traversal）技术是一种遍历树的方法，它会先完全遍历完当前层的所有节点，然后再进入下一层进行遍历。

> 输入:

> !112

> 输出: [[5], [12, 13], [7, 14, 2], [17, 23, 27, 3, 8, 11]]

> 解释: 从根节点开始 – [5]

> 第 1 层: [12, 13]

> 第 2 层: [7, 14, 2]

> 第 3 层: [17, 23, 27, 3, 8, 11]

目录

• [方法] 使用递归 – O(n) 时间和 O(n) 空间
• [推荐方法] 使用队列（迭代） – O(n) 时间和 O(n) 空间

[方法] 使用递归 – O(n) 时间和 O(n) 空间

> 我们的核心思路是从根节点（第 0 层）开始递归地遍历树。当我们访问一个节点时，将其值添加到结果数组中对应其层数的索引位置，然后以同样的方式递归处理其左子节点和右子节点。这实际上就是利用递归实现了层序遍历。

C++


CODEBLOCK_3a6ecca5


Java


“java

import java.util.ArrayList;

class Node {

int data;

Node left, right;

Node(int value)

{

data = value;

left = null;

right = null;

}

}

public class GfG {

void levelOrderRec(Node root, int level,

ArrayList<ArrayList> res)

{

// 基本情况

if (root == null)

return;

// 如果需要，在结果中添加一个新的层级

if (res.size() <= level)

res.add(new ArrayList());

// 将当前节点的数据添加到其对应的层级

res.get(level).add(root.data);

// 递归处理左右子节点

levelOrderRec(root.left, level + 1, res);

levelOrderRec(root.right, level + 1, res);

}

// 执行层序遍历的函数

ArrayList<ArrayList> levelOrder(Node root)

{

// 逐层存储结果

ArrayList<ArrayList> res = new ArrayList();

levelOrderRec(root, 0, res);

return res;

}

public static void main(String[] args)

{

// 5

// / \

// 12 13

// / \ \

// 7 14 2

// / \ / \ / \

//17 23 27 3 8 11

Node root = new Node(5);

root.left = new Node(12);

root.right = new Node(13);

root.left.left = new Node(7);

root.left.right = new Node(14);

root.right.right = new Node(2);

root.left.left.left = new Node(17);

root.left.left.right = new Node(23);

root.left.right.left = new Node(27);

root.left.right.right = new Node(3);

root.right.right.left = new Node(8);

root.right.right.right = new Node(11);

GfG tree = new GfG();

ArrayList<ArrayList> res = tree.levelOrder(root);

for (ArrayList level : res) {

for (int val : level) {

System.out.print(val