树专题 —— 二叉树层序遍历
站长
· 阅读数 11
大家好，我是 方圆。本篇关于二叉树的层序遍历，主要以题目为主，而且我觉得层序遍历是求解二叉树问题中最简单的，学会了基本的层序遍历，在这基础上的扩展题也能迎刃而解，如果大家想要找刷题路线的话，可以参考 Github: LeetCode。
层序遍历
我们可以一起先看一下 102. 二叉树的层序遍历，本题是最基本的层序遍历。我先把题解放在这里，之后再具体的解释下：
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> res = new LinkedList<>();
if (root == null) {
return res;
}
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
int size = queue.size();
List<Integer> element = new LinkedList<>();
for (int i = 0; i < size; i++) {
TreeNode node = queue.poll();
element.add(node.val);
if (node.left != null) {
queue.offer(node.left);
}
if (node.right != null) {
queue.offer(node.right);
}
}
res.add(element);
}
return res;
}
层序遍历顾名思义即逐层进行遍历，先将每层的节点存在 队列 当中，然后进行出队（取出当前层节点）和入队（存入下一层的节点）的操作，以此达到遍历的目的。
简单练习
二叉树的最小深度即找到最早出现的叶子节点，我们可以借助层序遍历每层每层地去找，一旦发现左右子树均为空的节点返回当前深度即可，题解如下：
public int minDepth(TreeNode root) {
int res = 0;
if (root == null) {
return res;
}
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
res++;
int size = queue.size();
for (int i = 0; i < size; i++) {
TreeNode node = queue.poll();
if (node.left == null && node.right == null) {
return res;
}
if (node.left != null) {
queue.offer(node.left);
}
if (node.right != null) {
queue.offer(node.right);
}
}
}
return res;
}
本题是非常直观的层序遍历变体，每层记录答案时使用链表，不断地变换头插法和尾插法即可，题解如下：
public List<List<Integer>> decorateRecord(TreeNode root) {
List<List<Integer>> res = new LinkedList<>();
if (root == null) {
return res;
}
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
boolean left = true;
while (!queue.isEmpty()) {
int size = queue.size();
LinkedList<Integer> element = new LinkedList<>();
for (int i = 0; i < size; i++) {
TreeNode node = queue.poll();
if (left) {
element.addLast(node.val);
} else {
element.addFirst(node.val);
}
if (node.left != null) {
queue.offer(node.left);
}
if (node.right != null) {
queue.offer(node.right);
}
}
left = !left;
res.add(element);
}
return res;
}
本题就更简单了，遍历每层时取该层的最右端元素即可，题解如下：
public List<Integer> rightSideView(TreeNode root) {
List<Integer> res = new LinkedList<>();
if (root == null) {
return res;
}
LinkedList<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
res.add(queue.peekLast().val);
int size = queue.size();
for (int i = 0; i < size; i++) {
TreeNode node = queue.poll();
if (node.left != null) {
queue.offer(node.left);
}
if (node.right != null) {
queue.offer(node.right);
}
}
}
return res;
}
进阶练习
接下来我们来看一些处理相对复杂的练习，但是它们的本质都是二叉树的层序遍历
在二叉树中添加一行，我觉得这道题的难点在于理解在插入这一行后节点间的引用关系该如何分配：
-
如果在 depth 为 1 时插入一行，这种为特殊情况，会改变根节点，需要特殊处理
-
如果在 depth > 1 的情况下插入一行，根节点引用是不变的，找到对应行之后，为所有节点添加值为 val 的左右子树，并将原来的左子树拼接在新左子树的左子树上，将原来的右子树拼接在新右子树的右子树上
public TreeNode addOneRow(TreeNode root, int val, int depth) {
if (depth == 1) {
TreeNode node = new TreeNode(val);
node.left = root;
return node;
}
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
int curDepth = 2;
while (!queue.isEmpty()) {
if (curDepth == depth) {
while (!queue.isEmpty()) {
TreeNode node = queue.poll();
TreeNode left = new TreeNode(val);
left.left = node.left;
node.left = left;
TreeNode right = new TreeNode(val);
right.right = node.right;
node.right = right;
}
break;
}
curDepth++;
int size = queue.size();
for (int i = 0; i < size; i++) {
TreeNode node = queue.poll();
if (node.left != null) {
queue.offer(node.left);
}
if (node.right != null) {
queue.offer(node.right);
}
}
}
return root;
}
本题在思路上不难，只是对应树节点索引值计算需要注意一下，为了求解方便，我们创建了 TreeNodeIndex 辅助记录节点和节点的索引信息。由于根节点的索引位置需要二叉树的高度作为参数才能计算出来，所以我们需要先求二叉树的高度，之后便是简单的层序遍历，在这个过程中只需要注意索引值的计算即可，题解如下：
static class TreeNodeIndex {
TreeNode node;
int m;
int n;
public TreeNodeIndex(TreeNode node, int m, int n) {
this.node = node;
this.m = m;
this.n = n;
}
}
public List<List<String>> printTree(TreeNode root) {
List<List<String>> res = new LinkedList<>();
int height = depth(root) - 1;
int n = (int) (Math.pow(2, height + 1) - 1);
ArrayList<String> element = new ArrayList<>();
for (int i = 0; i < n; i++) {
element.add("");
}
LinkedList<TreeNodeIndex> queue = new LinkedList<>();
queue.offer(new TreeNodeIndex(root, 0, (n - 1) / 2));
while (!queue.isEmpty()) {
int size = queue.size();
ArrayList<String> e = (ArrayList<String>) element.clone();
for (int i = 0; i < size; i++) {
TreeNodeIndex node = queue.poll();
e.set(node.n, String.valueOf(node.node.val));
int commonValue = (int) Math.pow(2, height - node.m - 1);
if (node.node.left != null) {
queue.offer(new TreeNodeIndex(node.node.left, node.m + 1, node.n - commonValue));
}
if (node.node.right != null) {
queue.offer(new TreeNodeIndex(node.node.right, node.m + 1, node.n + commonValue));
}
}
res.add(e);
}
return res;
}
private int depth(TreeNode root) {
if (root == null) {
return 0;
}
int left = depth(root.left);
int right = depth(root.right);
return Math.max(left, right) + 1;
}
垂序遍历的思路并不难，大家需要做的是借助层序遍历计算所有节点的索引，根据题目的排序规则将所有的节点加入到优先队列中，之后按照同一列为一组元素组合成答案即可，题解如下：
static class TreeNodeIndex implements Comparable<TreeNodeIndex> {
int x;
int y;
TreeNode node;
public TreeNodeIndex(int x, int y, TreeNode node) {
this.x = x;
this.y = y;
this.node = node;
}
@Override
public int compareTo(TreeNodeIndex o) {
if (this.y == o.y) {
if (this.x == o.x) {
return this.node.val - o.node.val;
} else {
return this.x - o.x;
}
} else {
return this.y - o.y;
}
}
}
public List<List<Integer>> verticalTraversal(TreeNode root) {
TreeNodeIndex rootNode = new TreeNodeIndex(0, 0, root);
Queue<TreeNodeIndex> queue = new LinkedList<>();
queue.offer(rootNode);
PriorityQueue<TreeNodeIndex> priorityQueue = new PriorityQueue<>();
priorityQueue.offer(rootNode);
while (!queue.isEmpty()) {
int size = queue.size();
for (int i = 0; i < size; i++) {
TreeNodeIndex node = queue.poll();
if (node.node.left != null) {
TreeNodeIndex left = new TreeNodeIndex(node.x + 1, node.y - 1, node.node.left);
priorityQueue.offer(left);
queue.offer(left);
}
if (node.node.right != null) {
TreeNodeIndex right = new TreeNodeIndex(node.x + 1, node.y + 1, node.node.right);
priorityQueue.offer(right);
queue.offer(right);
}
}
}
List<List<Integer>> res = new LinkedList<>();
while (!priorityQueue.isEmpty()) {
TreeNodeIndex peek = priorityQueue.peek();
LinkedList<Integer> element = new LinkedList<>();
while (!priorityQueue.isEmpty() && priorityQueue.peek().y == peek.y) {
element.add(priorityQueue.poll().node.val);
}
res.add(element);
}
return res;
}
之前我们写过 449. 序列化和反序列化二叉搜索树 中等，因为二叉搜索树节点间有大小关系能够区分去根节点和左右子树，所以它的序列化思路和普通二叉树序列化思路并不相同。普通二叉树的序列化和反序列化可以层序遍历来实现，与我们平时写的层序遍历不同的是：我们需要将其中所有的非空节点也记录下来，这样我们才能确定每个节点所在的合适的位置，它并不是很难，参考代码如下：
// Encodes a tree to a single string.
public String serialize(TreeNode root) {
if (root == null) {
return "";
}
StringBuilder res = new StringBuilder();
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
int size = queue.size();
for (int i = 0; i < size; i++) {
TreeNode node = queue.poll();
if (node == null) {
res.append("null").append(",");
} else {
res.append(node.val).append(",");
queue.offer(node.left);
queue.offer(node.right);
}
}
}
return res.toString();
}
// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
if ("".equals(data)) {
return null;
}
String[] nodes = data.split(",");
TreeNode root = new TreeNode(Integer.parseInt(nodes[0]));
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
int index = 1;
while (index < nodes.length) {
int size = queue.size();
for (int i = 0; i < size; i++) {
TreeNode node = queue.poll();
if ("null".equals(nodes[index])) {
node.left = null;
} else {
TreeNode left = new TreeNode(Integer.parseInt(nodes[index]));
node.left = left;
queue.offer(left);
}
index++;
if ("null".equals(nodes[index])) {
node.right = null;
} else {
TreeNode right = new TreeNode(Integer.parseInt(nodes[index]));
node.right = right;
queue.offer(right);
}
index++;
}
}
return root;
}