第三章：二叉树问题（四）
二叉树的按层打印与ZigZag打印
【题目】
给定一棵二叉树的头节点head，分别实现按层和ZigZag打印二叉树的函数。
例如，二叉树如图3-29所示。
按层打印时，输出格式必须如下：
Level 1 : 1
Level 2 : 2 3
Level 3 : 4 5 6
Level 4 : 7 8
ZigZag打印时，输出格式必须如下：
Level 1 from left to right: 1
Level 2 from right to left: 3 2
Level 3 from left to right: 4 5 6
Level 4 from right to left: 8 7
【难度】
尉 ★★☆☆
【解答】
按层打印的实现
按层打印原本是十分基础的内容，对二叉树做简单的宽度优先遍历即可，但本题有额外的要求，那就是同一层的节点必须打印在一行上，并且要求输出行号。这就需要我们在原来宽度优先遍历的基础上做一些改进，所以关键问题是如何知道该换行。只需要用两个node类型的变量last和nLast就可以解决这个问题，last变量表示正在打印的当前行的最右节点，nLast表示下一行的最右节点。假设我们每一层都做从左到右的宽度优先遍历，如果发现遍历到的节点等于last，则说明应该换行。换行之后，只要令last=nLast，就可以继续下一行的打印过程，重复此过程，直到所有的节点都打印完。那么问题就变成了如何更新nLast？只需要让nLast一直跟踪记录宽度优先队列中的最新加入的节点即可。这是因为最新加入队列的节点一定是目前已经发现的下一行的最右节点。所以在当前行打印完时，nLast一定是下一行所有节点中的最右节点。接下来结合题目的例子来说明整个过程。
开始时，last=节点1，nLast=null，把节点1放入队列queue，遍历开始，queue={1}。
从queue中弹出节点1并打印，然后把节点1的孩子节点依次放入queue，放入节点2时，nLast=节点2，放入节点3时，nLast=节点3，此时发现弹出的节点1==last，所以换行，并令last=nLast=节点3，queue={2,3}。
从queue中弹出节点2并打印，然后把节点2的孩子节点放入queue，放入节点4时，nLast=节点4，queue={3,4}。
从queue中弹出节点3并打印，然后把节点3的孩子节点放入queue，放入节点5时，nLast=节点5，放入节点6时，nLast=节点6，此时发现弹出的节点3==last，所以换行，并令last=nLast=节点6，queue={4,5,6}。
从queue中弹出节点4并打印，节点4没有孩子节点，所以不放入任何节点，nLast也不更新。
从queue中弹出节点5并打印，然后把节点5的孩子节点依次放入queue，放入节点7时，nLast=节点7，放入节点8时，nLast=节点8，queue={6,7,8}。
从queue中弹出节点6并打印，节点6没有孩子节点，所以不放入任何节点，nLast也不更新，此时发现弹出的节点6==last。所以换行，并令last=nLast=节点8，queue={7,8}。
用同样的判断过程打印节点7和节点8，整个过程结束。
按层打印的详细过程请参看如下代码中的printByLevel方法。
public class Node {
public int value;
public Node left;
public Node right;
public Node(int data) {
this.value = data;
}
}
public void printByLevel(Node head) {
if (head == null) {
return;
}
Queue<Node> queue = new LinkedList<Node>();
int level = 1;
Node last = head;
Node nLast = null;
queue.offer(head);
System.out.print("Level " + (level++) + " : ");
while (!queue.isEmpty()) {
head = queue.poll();
System.out.print(head.value + " ");
if (head.left != null) {
queue.offer(head.left);
nLast = head.left;
}
if (head.right != null) {
queue.offer(head.right);
nLast = head.right;
}
if (head == last && !queue.isEmpty()) {
System.out.print("\nLevel " + (level++) + " : ");
last = nLast;
}
}
System.out.println();
} ZigZag打印的实现
先简单介绍一种不推荐的方法，即使用ArrayList结构的方法。两个ArrayList结构记为list1和list2，用list1收集当前层的节点，然后从左到右打印当前层，接着把当前层的孩子节点放进list2，并从右到左打印，接下来再把list2的所有节点的孩子节点放入list1，如此反复。不推荐的原因是ArrayList结构为动态数组，在这个结构中，当元素数量到一定规模时将发生扩容操作，扩容操作的时间复杂度为O(N)，是比较高的，这个结构增加和删除元素的时间复杂度也较高。总之，对本题来讲，用这个结构时数据结构不够“纯粹”和“干净”，而且还需要两个ArrayList结构，如果读者不充分理解这个结构的底层实现，最好不要使用。
本书提供的方法只使用了一个双端队列，具体为Java中的LinkedList结构，这个结构的底层实现就是非常纯粹的双端队列结构，本书的方法也仅使用双端队列结构的基本操作。
先举题目的例子来展示大体过程，首先生成双端队列结构dq，将节点1从dq的头部放入dq。
原则1：如果是从左到右的过程。那么一律从dq的头部弹出节点，如果弹出的节点没有孩子节点，当然不用放入任何节点到dq中；如果当前节点有孩子节点，先让左孩子节点从尾部进入dq，再让右孩子节点从尾部进入dq。
根据原则1，先从dq头部弹出节点1并打印，然后先让节点2从dq尾部进入，再让节点3从dq尾部进入，如图3-30所示。
原则2：如果是从右到左的过程，那么一律从dq的尾部弹出节点，如果弹出的节点没有孩子节点，当然不用放入任何节点到dq中；如果当前节点有孩子节点，先让右孩子从头部进入dq，再让左孩子节点从头部进入dq。
根据原则2，先从dq尾部弹出节点3并打印，然后先让节点6从dq头部进入，再让节点5从dq头部进入，如图3-31所示。
根据原则2，先从dq尾部弹出节点2并打印，然后让节点4从dq头部进入，如图3-32所示。
根据原则1，依次从dq头部弹出节点4、5、6并打印，这期间先让节点7从dq尾部进入，再让节点8从dq尾部进入，如图3-33所示。
最后根据原则2，依次从dq尾部弹出节点8和7并打印即可。
用原则1和原则2的过程切换，我们可以完成ZigZag的打印过程，所以现在只剩一个问题：如何确定切换原则1和原则2的时机？这其实还是如何确定每一层最后一个节点的问题。
在ZigZag的打印过程中，下一层最后打印的节点是当前层有孩子节点的节点中最先进入dq的节点。比如，处理第1层的第1个有孩子节点的节点，也就是节点1时，节点1的左孩子节点2最先进入的dq，那么节点2就是下一层打印时的最后一个节点。处理第2层的第一个有孩子的节点，也就是节点3时，节点3的右孩子节点6最先进入的dq，那么节点6就是下一层打印时的最后一个节点。处理第3层的第一个有孩子节点的节点，也就是节点5时，节点5的左孩子节点7最先进的dq，那么节点7就是下一层打印时的最后一个节点。
ZigZag打印的全部过程请参看如下代码中的printByZigZag方法。
public void printByZigZag(Node head) {
if (head == null) {
return;
}
Deque<Node> dq = new LinkedList<Node>();
int level = 1;
boolean lr = true;
Node last = head;
Node nLast = null;
dq.offerFirst(head);
pringLevelAndOrientation(level++, lr);
while (!dq.isEmpty()) {
if (lr) {
head = dq.pollFirst();
if (head.left != null) {
nLast = nLast == null ? head.left : nLast;
dq.offerLast(head.left);
}
if (head.right != null) {
nLast = nLast == null ? head.right : nLast;
dq.offerLast(head.right);
}
} else {
head = dq.pollLast();
if (head.right != null) {
nLast = nLast == null ? head.right : nLast;
dq.offerFirst(head.right);
}
if (head.left != null) {
nLast = nLast == null ? head.left : nLast;
dq.offerFirst(head.left);
}
}
System.out.print(head.value + " ");
if (head == last && !dq.isEmpty()) {
lr = !lr;
last = nLast;
nLast = null;
System.out.println();
pringLevelAndOrientation(level++, lr);
}
}
System.out.println();
}
public void pringLevelAndOrientation(int level, boolean lr) {
System.out.print("Level " + level + " from ");
System.out.print(lr ? "left to right: " : "right to left: ");
}
调整搜索二叉树中两个错误的节点
【题目】
一棵二叉树原本是搜索二叉树，但是其中有两个节点调换了位置，使得这棵二叉树不再是搜索二叉树，请找到这两个错误节点并返回。已知二叉树中所有节点的值都不一样，给定二叉树的头节点head，返回一个长度为2的二叉树节点类型的数组errs，errs[0]表示一个错误节点，errs[1]表示另一个错误节点。
进阶问题：如果在原问题中得到了这两个错误节点，我们当然可以通过交换两个节点的节点值的方式让整棵二叉树重新成为搜索二叉树。但现在要求你不能这么做，而是在结构上完全交换两个节点的位置，请实现调整的函数。
【难度】
原问题 尉 ★★☆☆
进阶问题 将 ★★★★
【解答】
原问题——找到这两个错误节点。如果对所有的节点值都不一样的搜索二叉树进行中序遍历，那么出现的节点值会一直升序。因此，如果有两个节点位置错了，就一定会出现降序。
如果在中序遍历时节点值出现了两次降序，第一个错误的节点为第一次降序时较大的节点，第二个错误的节点为第二次降序时较小的节点。
比如，原来的搜索二叉树在中序遍历时的节点值依次出现{1,2,3,4,5}，如果因为两个节点位置错了而出现{1,5,3,4,2}，第一次降序为5->3，所以第一个错误节点为5，第二次降序为4->2，所以第二个错误节点为2，把5和2换过来就可以恢复。
如果在中序遍历时节点值只出现了一次降序，第一个错误的节点为这次降序时较大的节点，第二个错误的节点为这次降序时较小的节点。
比如，原来的搜索二叉树在中序遍历时节点值依次出现{1,2,3,4,5}，如果因为两个节点位置错了而出现{1,2,4,3,5}，只有一次降序为4->3，所以第一个错误节点为4，第二个错误节点为3，把4和3换过来就可以恢复。
寻找两个错误节点的过程可以总结为：第一个错误节点为第一次降序时较大的节点，第二个错误节点为最后一次降序时较小的节点。
因此，只要改写一个基本的中序遍历，就可以完成原问题的要求，改写递归、非递归或者Morris遍历都可以。
找到两个错误节点的过程请参看如下代码中的getTwoErrNodes方法。
public class Node {
public int value;
public Node left;
public Node right;
public Node(int data) {
this.value = data;
}
}
public Node[] getTwoErrNodes(Node head) {
Node[] errs = new Node[2];
if (head == null) {
return errs;
}
Stack<Node> stack = new Stack<Node>();
Node pre = null;
while (!stack.isEmpty() || head != null) {
if (head != null) {
stack.push(head);
head = head.left;
} else {
head = stack.pop();
if (pre != null && pre.value > head.value) {
errs[0] = errs[0] == null ? pre : errs[0];
errs[1] = head;
}
pre = head;
head = head.right;
}
}
return errs;
}
进阶问题——在结构上交换这两个错误节点。若要在结构上交换两个错误节点，首先应该找到两个错误节点各自的父节点，再随便改写一个二叉树的遍历即可。
找到两个错误节点各自父节点的过程请参看如下代码中的getTwoErrParents方法，该方法返回长度为2的Node类型的数组parents，parents[0]表示第一个错误节点的父节点，parents[1]表示第二个错误节点的父节点。
public Node[] getTwoErrParents(Node head, Node e1, Node e2) {
Node[] parents = new Node[2];
if (head == null) {
return parents;
}
Stack<Node> stack = new Stack<Node>();
while (!stack.isEmpty() || head != null) {
if (head != null) {
stack.push(head);
head = head.left;
} else {
head = stack.pop();
if (head.left == e1 || head.right == e1) {
parents[0] = head;
}
if (head.left == e2 || head.right == e2) {
parents[1] = head;
}
head = head.right;
}
}
return parents;
} 找到两个错误节点的父节点之后，第一个错误节点记为e1，e1的父节点记为e1P，e1的左孩子节点记为e1L，e1的右孩子节点记为e1R。第二个错误节点记为e2，e2的父节点记为e2P，e2的左孩子节点记为e2L，e2的右孩子节点记为e2R。
在结构上交换两个节点，实际上就是把两个节点互换环境。简单地讲，就是让e2成为e1P的孩子节点，让e1L和e1R成为e2的孩子节点；让e1成为e2P的孩子节点，让e2L和e2R成为e1的孩子节点。但这只是简单地理解，在实际交换的过程中有很多情况需要我们做特殊处理。比如，如果e1是头节点，则意味着e1P为null，那么让e2成为e1P的孩子节点时，关于e1P的任何left指针或right指针操作都会发生错误，因为e1P为null则根本没有Node类型节点的结构。再如，如果e1本身就是e2的左孩子节点，即e1==e2L，那么让e2L成为e1的左孩子节点时，e1的left指针将指向e2L，将会指向自己，这会让整棵二叉树发生严重的结构错误。
换句话说，我们必须理清楚e1及其上下环境之间的关系，e2及其上下环境之间的关系，以及两个环境之间是否有联系。有以下三个问题和一个特别注意是必须关注的。
问题一：e1和e2是否有一个是头节点？如果有，谁是头节点？
问题二：e1和e2是否相邻？如果相邻，谁是谁的父节点？
问题三：e1和e2分别是各自父节点的左孩子节点还是右孩子节点？
特别注意：因为是在中序遍历时先找到e1，后找到e2，所以e1一定不是e2的右孩子节点，e2也一定不是e1的左孩子节点。
以上三个问题与特别注意之间相互影响，情况非常复杂。经过仔细整理，共有14种情况，每一种情况在调整e1和e2各自的拓扑关系时都有特殊处理。
1．e1是头节点，e1是e2的父节点，此时e2只可能是e1的右孩子节点。
2．e1是头节点，e1不是e2的父节点，e2是e2P的左孩子节点。
3．e1是头节点，e1不是e2的父节点，e2是e2P的右孩子节点。
4．e2是头节点，e2是e1的父节点，此时e1只可能是e2的左孩子节点。
5．e2是头节点，e2不是e1的父节点，e1是e1P的左孩子节点。
6．e2是头节点，e2不是e1的父节点，e1是e1P的右孩子节点。
7．e1和e2都不是头节点，e1是e2的父节点，此时e2只可能是e1的右孩子节点，e1是e1P的左孩子节点。
8．e1和e2都不是头节点，e1是e2的父节点，此时e2只可能是e1的右孩子节点，e1是e1P的右孩子节点。
9．e1和e2都不是头节点，e2是e1的父节点，此时e1只可能是e2的左孩子节点，e2是e2P的左孩子节点。
10．e1和e2都不是头节点，e2是e1的父节点，此时e1只可能是e2的左孩子节点，e2是e2P的右孩子节点。
11．e1和e2都不是头节点，谁也不是谁的父节点，e1是e1P的左孩子节点，e2是e2P的左孩子节点。
12．e1和e2都不是头节点，谁也不是谁的父节点，e1是e1P的左孩子节点，e2是e2P的右孩子节点。
13．e1和e2都不是头节点，谁也不是谁的父节点，e1是e1P的右孩子节点，e2是e2P的左孩子节点。
14．e1和e2都不是头节点，谁也不是谁的父节点，e1是e1P的右孩子节点，e2是e2P的右孩子节点。
当情况1至情况3发生时，二叉树新的头节点应该为e2，当情况4至情况6发生时，二叉树新的头节点应该为e1，其他情况发生时，二叉树的头节点不用发生变化。
从结构上调整两个错误节点的全部过程请参看如下代码中的recoverTree方法。
public Node recoverTree(Node head) {
Node[] errs = getTwoErrNodes(head);
Node[] parents = getTwoErrParents(head, errs[0], errs[1]);
Node e1 = errs[0];
Node e1P = parents[0];
Node e1L = e1.left;
Node e1R = e1.right;
Node e2 = errs[1];
Node e2P = parents[1];
Node e2L = e2.left;
Node e2R = e2.right;
if (e1 == head) {
if (e1 == e2P) { // 情况1
e1.left = e2L;
e1.right = e2R;
e2.right = e1;
e2.left = e1L;
} else if (e2P.left == e2) { // 情况2
e2P.left = e1;
e2.left = e1L;
e2.right = e1R;
e1.left = e2L;
e1.right = e2R;
} else { // 情况3
e2P.right = e1;
e2.left = e1L;
e2.right = e1R;
e1.left = e2L;
e1.right = e2R;
}
head = e2;
} else if (e2 == head) {
if (e2 == e1P) { // 情况4
e2.left = e1L;
e2.right = e1R;
e1.left = e2;
e1.right = e2R;
} else if (e1P.left == e1) { // 情况5
e1P.left = e2;
e1.left = e2L;
e1.right = e2R;
e2.left = e1L;
e2.right = e1R;
} else { // 情况6
e1P.right = e2;
e1.left = e2L;
e1.right = e2R;
e2.left = e1L;
e2.right = e1R;
}
head = e1;
} else {
if (e1 == e2P) {
if (e1P.left == e1) { // 情况7
e1P.left = e2;
e1.left = e2L;
e1.right = e2R;
e2.left = e1L;
e2.right = e1;
} else { // 情况8
e1P.right = e2;
e1.left = e2L;
e1.right = e2R;
e2.left = e1L;
e2.right = e1;
}
} else if (e2 == e1P) {
if (e2P.left == e2) { // 情况9
e2P.left = e1;
e2.left = e1L;
e2.right = e1R;
e1.left = e2;
e1.right = e2R;
} else { // 情况10
e2P.right = e1;
e2.left = e1L;
e2.right = e1R;
e1.left = e2;
e1.right = e2R;
}
} else {
if (e1P.left == e1) {
if (e2P.left == e2) { // 情况11
e1.left = e2L;
e1.right = e2R;
e2.left = e1L;
e2.right = e1R;
e1P.left = e2;
e2P.left = e1;
} else { // 情况12
e1.left = e2L;
e1.right = e2R;
e2.left = e1L;
e2.right = e1R;
e1P.left = e2;
e2P.right = e1;
}
} else {
if (e2P.left == e2) { // 情况13
e1.left = e2L;
e1.right = e2R;
e2.left = e1L;
e2.right = e1R;
e1P.right = e2;
e2P.left = e1;
} else { // 情况14
e1.left = e2L;
e1.right = e2R;
e2.left = e1L;
e2.right = e1R;
e1P.right = e2;
e2P.right = e1;
}
}
}
}
return head;
}
<p> 本专刊为左程云书《程序员代码面试指南》前三章，已获得官方授权，想看书中更多内容可去购买书籍查看。 同时点击可查看牛客算法笔面试真题精讲班，每周由左老师讲解经典高频校招题目：https://www.nowcoder.com/courses/cover/live/350 本专刊购买后即可解锁所有章节，故不可以退换哦~ </p> <p> <br /> </p>
每次去实验室都得接一杯免费的开水回去，出门都得规划一下最短路径，在宿舍就吃南边的食堂，在实验室就吃北边的食堂，快递只有顺路的时候才取。
