第三章：二叉树问题（二）

如何较为直观地打印二叉树

【题目】

二叉树可以用常规的三种遍历结果来描述其结构，但是不够直观，尤其是二叉树中有重复值的时候，仅通过三种遍历的结果来构造二叉树的真实结构更是难上加难，有时则根本不可能。给定一棵二叉树的头节点head，已知二叉树节点值的类型为32位整型，请实现一个打印二叉树的函数，可以直观地展示树的形状，也便于画出真实的结构。

【难度】

尉     ★★☆☆

【解答】

这是一道较开放的题目，实现者不仅要设计出符合要求且不会产生歧义的打印方式，还要考虑实现难度，在面试时仅仅写出思路必然是不满足代码面试要求的。本书给出一种符合要求且代码量不大的实现，希望读者也能实现并优化自己的设计。具体过程如下：

1．设计打印的样式。实现者首先应该解决的问题是用什么样的方式来无歧义地打印二叉树。比如，二叉树如图3-4所示。

下面解释一下如何看打印的结果。首先，二叉树大概的样子是把打印结果顺时针旋转90°，读者可以把图3-4的打印结果（也就是图3-5顺时针旋转90°之后）做对比，两幅图是存在明显对应关系的；接下来，怎么清晰地确定任何一个节点的父节点呢？如果一个节点打印结果的前缀与后缀都有“H”（如图3-5中的“H1H”），则说明这个节点是头节点，当然就不存在父节点。如果一个节点打印结果的前缀与后缀都有“v”，则表示父节点在该节点所在列的前一列，在该节点所在行的下方，并且是离该节点最近的节点。比如，图3-5中的“v3v”“v6v”和“v7v”，父节点分别为“H1H”“v3v”和“^4^”。如果一个节点打印结果的前缀与后缀都有“^”，则表示父节点在该节点所在列的前一列，在该节点所在行的上方，并且是离该节点最近的节点。比如，图3-5中的“^5^”“^2^”和“^4^”，父节点分别为“v3v”“H1H”和“^2^”。

2．一个需要重点考虑的问题——规定节点打印时占用的统一长度。我们必须规定一个节点在打印时到底占多长。试想一下，如果有些节点的值本身的长度很短，如“1”“2”等，而有些节点的值本身的长度很长，如“43323232”“78787237”等，那么如果不规定一个统一的长度，则在打印一个长短值交替的二叉树时必然会出现格式对不齐的问题，进而产生歧义。在Java中，整型值占用长度最长的值是Integer.MIN_VALUE（-2147483648），占用的长度为11，加上前缀和后缀（“H”“v”或“^”）之后占用长度为13。为了在打印之后更好地区分，再把前面加上两个空格，后面加上两个空格，总共占用长度为17。也就是说，长度为17的空间必然可以放下任何一个32位整数，同时样式还不错。至此，我们约定，打印每一个节点时，必须让每一个节点在打印时占用长度都为17，如果不足，则前后都用空格补齐。比如，节点值为8，假设这个节点加上“v”作为前后缀，那么实质内容为“v8v”，长度才为3，在打印时在“v8v”的前面补7个空格，后面也补7个空格，让总长度为17。再如，节点值为66，假设这个节点加上“v”作为前后缀，那么实质内容为“v66v”，长度才为4，在打印时在“v66v”的前面补6个空格，后面补7个空格，让总长度为17。总之，如果长度不足，则前后贴上几乎数量相等的空格来补齐。

3．确定了打印的样式，规定了占用长度的标准，最后来解释具体的实现。打印的整体过程结合了二叉树先右子树、再根节点、最后左子树的递归遍历过程。如果递归到一个节点，则首先遍历它的右子树。右子树遍历结束后，回到这个节点。如果这个节点所在层为l，那么先打印l´17个空格（不换行），然后开始制作该节点的打印内容，这个内容当然包括节点的值，以及确定的前后缀字符。如果该节点是其父节点的右孩子节点，则前后缀为“v”，如果该节点是其父节点的左孩子节点，则前后缀为“^”，如果是头节点，则前后缀为“H”。最后在前后分别贴上数量几乎一致的空格，占用长度为17的打印内容就制作完成，打印这个内容后换行。最后进行左子树的遍历过程。

直观地打印二叉树的所有过程请参看如下代码中的printTree方法。

	public class Node {
		public int value;
		public Node left;
		public Node right;

		public Node(int data) {
			this.value = data;
		}
	}

	public void printTree(Node head) {
		System.out.println("Binary Tree:");
		printInOrder(head, 0, "H", 17);
		System.out.println();
	}

	public void printInOrder(Node head, int height, String to, int len) {
		if (head == null) {
			return;
		}
		printInOrder(head.right, height + 1, "v", len);
		String val = to + head.value + to;
		int lenM = val.length();
		int lenL = (len - lenM) / 2;
		int lenR = len - lenM - lenL;
		val = getSpace(lenL) + val + getSpace(lenR);
		System.out.println(getSpace(height * len) + val);
		printInOrder(head.left, height + 1, "^", len);
	}

	public String getSpace(int num) {
		String space = " ";
		StringBuffer buf = new StringBuffer("");
		for (int i = 0; i < num; i++) {
			buf.append(space);
		}
		return buf.toString();
	}

【扩展】

有关功能设计的面试题，其实最难的部分并不是设计，而是在设计的优良性和实现的复杂程度之间找到一个平衡性最好的设计方案。在满足功能要求的同时，也要保证在面试场上能够完成大致的代码实现，同时，对边界条件的梳理能力和代码逻辑的实现能力也是一大挑战。读者可以看到本书提供的方法在完成功能的同时其代码很少，也请读者设计自己的方案并实现它。

二叉树的序列化和反序列化

【题目】

二叉树被记录成文件的过程叫作二叉树的序列化，通过文件内容重建原来二叉树的过程叫作二叉树的反序列化。给定一棵二叉树的头节点head，已知二叉树节点值的类型为32位整型。请设计一种二叉树序列化和反序列化的方案，并用代码实现。

【难度】

士     ★☆☆☆

【解答】

本书提供两套序列化和反序列化的实现，供读者参考。

方法一：通过先序遍历实现序列化和反序列化。

先介绍先序遍历下的序列化过程，首先假设序列化的结果字符串为str，初始时str=""。先序遍历二叉树，如果遇到null节点，就在str的末尾加上“#!”，“#”表示这个节点为空，节点值不存在，“!”表示一个值的结束；如果遇到不为空的节点，假设节点值为3，就在str的末尾加上“3!”。比如，如图3-6所示的二叉树。

根据上文的描述，先序遍历序列化，最后的结果字符串str为：12!3!#!#!#!。

为什么要在每个节点值的后面都要加上“!”呢？因为，如果不标记一个值的结束，那么最后产生的结果会有歧义，如图3-7所示。

如果不在一个值结束时加入特殊字符，那么图3-6和图3-7的先序遍历序列化结果都是123###。也就是说，生成的字符串并不代表唯一的树。

先序遍历序列化的全部过程请参看如下代码中的serialByPre方法。

	public class Node {
		public int value;
		public Node left;
		public Node right;

		public Node(int data) {
			this.value = data;
		}
	}

	public String serialByPre(Node head) {
		if (head == null) {
			return "#!";
		}
		String res = head.value + "!";
		res += serialByPre(head.left);
		res += serialByPre(head.right);
		return res;
	}

接下来介绍如何通过先序遍历序列化的结果字符串str，重构二叉树的过程，即反序列化。

把结果字符串str变成字符串类型的数组，记为values，数组代表一棵二叉树先序遍历的节点顺序。例如，str="12!3!#!#!#! "，生成的values为["12","3","#","#","#"]，然后用values[0..4]按照先序遍历的顺序建立整棵树。

1．遇到"12"，生成节点值为12的节点（head），然后用values[1..4]建立节点12的左子树。

2．遇到"3"，生成节点值为3的节点，它是节点12的左孩子节点，然后用values[2..4]建立节点3的左子树。

3．遇到"#"，生成null节点，它是节点3的左孩子节点，该节点为null，所以这个节点没有后续建立子树的过程。回到节点3后，用values[3..4]建立节点3的右子树。

4．遇到"#"，生成null节点，它是节点3的右孩子节点，该节点为null，所以这个节点没有后续建立子树的过程。回到节点3后，再回到节点1，用values[4]建立节点1的右子树。

5．遇到"#"，生成null节点，它是节点1的右孩子节点，该节点为null，所以这个节点没有后续建立子树的过程。整个过程结束。

先序遍历反序列化的全部过程请参看如下代码中的reconByPreString方法。

	public Node reconByPreString(String preStr) {
		String[] values = preStr.split("!");
		Queue<String> queue = new LinkedList<String>();
		for (int i = 0; i != values.length; i++) {
			queue.offer(values[i]);
		}
		return reconPreOrder(queue);
	}

	public Node reconPreOrder(Queue<String> queue) {
		String value = queue.poll();
		if (value.equals("#")) {
			return null;
		}
		Node head = new Node(Integer.valueOf(value));
		head.left = reconPreOrder(queue);
		head.right = reconPreOrder(queue);
		return head;
	} 

方法二：通过层遍历实现序列化和反序列化。

先介绍层遍历下的序列化过程。首先假设序列化的结果字符串为str，初始时str="空"。然后实现二叉树的按层遍历，具体方式是利用队列结构，这也是宽度遍历图的常见方式。例如，图3-8所示的二叉树。

按层遍历图3-8所示的二叉树，最后str="1!2!3!4!#!#!5!#!#!#!#! "。

层遍历序列化的全部过程请参看如下代码中的serialByLevel方法。

	public String serialByLevel(Node head) {
		if (head == null) {
			return "#!";
		}
		String res = head.value + "!";
		Queue<Node> queue = new LinkedList<Node>();
		queue.offer(head);
		while (!queue.isEmpty()) {
			head = queue.poll();
			if (head.left != null) {
				res += head.left.value + "!";
				queue.offer(head.left);
			} else {
				res += "#!";
			}
			if (head.right != null) {
				res += head.right.value + "!";
				queue.offer(head.right);
			} else {
				res += "#!";
			}
		}
		return res;
	}

先序遍历的反序列化其实就是重做先序遍历，遇到"#"就生成null节点，结束生成后续子树的过程。

与根据先序遍历的反序列化过程一样，根据层遍历的反序列化是重做层遍历，遇到"#"就生成null节点，同时不把null节点放到队列里即可。

层遍历反序列化的全部过程请参看如下代码中的reconByLevelString方法。

	public Node reconByLevelString(String levelStr) {
		String[] values = levelStr.split("!");
		int index = 0;
		Node head = generateNodeByString(values[index++]);
		Queue<Node> queue = new LinkedList<Node>();
		if (head != null) {
			queue.offer(head);
		}
		Node node = null;
		while (!queue.isEmpty()) {
			node = queue.poll();
			node.left = generateNodeByString(values[index++]);
			node.right = generateNodeByString(values[index++]);
			if (node.left != null) {
				queue.offer(node.left);
			}
			if (node.right != null) {
				queue.offer(node.right);
			}
		}
		return head;
	}

	public Node generateNodeByString(String val) {
		if (val.equals("#")) {
			return null;
		}
		return new Node(Integer.valueOf(val));
	}

遍历二叉树的神级方法

【题目】

给定一棵二叉树的头节点head，完成二叉树的先序、中序和后序遍历。如果二叉树的节点数为N，则要求时间复杂度为O(N)，额外空间复杂度为O(1)。

【难度】

将     ★★★★

【解答】

本题真正的难点在于对复杂度的要求，尤其是额外空间复杂度为O(1)的限制。之前的题目已经剖析过如何用递归和非递归的方法实现遍历二叉树，但是很不幸，之前所有的方法虽然常用，但都无法做到额外空间复杂度为O(1)。这是因为遍历二叉树的递归方法实际使用了函数栈，非递归的方法使用了申请的栈，两者的额外空间都与树的高度相关，所以空间复杂度为O(h)，h为二叉树的高度。如果完全不用栈结构能完成三种遍历吗？答案是可以。方法是使用二叉树节点中大量指向null的指针，本题实际上就是大名鼎鼎的Morris遍历，由Joseph Morris于1979年发明。

首先来看普通的递归和非递归解法，其实都使用了栈结构，在处理完二叉树某个节点后可以回到上层去。为什么从下层回到上层会如此之难？因为二叉树的结构如此，每个节点都有指向孩子节点的指针，所以从上层到下层容易，但是没有指向父节点的指针，所以从下层到上层需要用栈结构辅助完成。

Morris遍历的实质就是避免用栈结构，而是让下层到上层有指针，具体是通过让底层节点指向null的空闲指针指回上层的某个节点，从而完成下层到上层的移动。我们知道，二叉树上的很多节点都有大量的空闲指针，比如，某些节点没有右孩子节点，那么这个节点的right指针就指向null，我们称为空闲状态，Morris遍历正是利用了这些空闲指针。

我们先不管先序、中序、后序的概念，先看看Morris遍历的过程。

假设当前节点为cur，初始时cur就是整棵树的头节点，根据以下标准让cur移动：

1．如果cur为null，则过程停止，否则继续下面的过程。

2．如果cur没有左子树，则让cur向右移动，即令cur = cur.right。

3．如果cur有左子树，则找到cur左子树上最右的节点，记为mostRight。

1）如果mostRight的right指针指向null，则令mostRight.right = cur，也就是让mostRight的right指针指向当前节点，然后让cur向左移动，即令cur = cur.left。

2）如果mostRight的right指针指向cur，则令mostRight.right = null，也就是让mostRight的right指针指向null，然后让cur向右移动，即令cur = cur.right。

以上标准并不复杂，下面用例子来展示遍历过程，假设一棵二叉树如图3-9所示。

1．初始时cur来到节点4，cur此时有左子树，所以根据刚才介绍的标准，找到cur的左子树最右节点（即节点3），发现节点3的右指针是指向空的，那么让其指向cur，树被调整成如图3-10所示的样子，然后cur向左移动来到节点2。

2．cur来到节点2，cur此时有左子树，找到cur的左子树最右节点（即节点1），发现节点1的右指针是指向空的，那么让其指向cur，树被调整成如图3-11所示的样子，然后cur向左移动来到节点1。

 

3．cur来到节点1，cur此时没有左子树，根据标准令cur向右指针方向移动，所以cur回到了节点2。

4．cur来到节点2，cur此时有左子树，找到cur的左子树最右节点，即节点1，发现节点1的右指针是指向cur的，根据标准让其指向null，树被调整回如图3-10所示的样子，然后根据标准，cur向右指针方向移动，所以cur来到了节点3。

5．cur来到节点3，cur此时没有左子树，根据标准令cur向右指针方向移动，所以cur回到了节点4。

6．cur来到节点4，cur此时有左子树，找到cur的左子树最右节点，即节点3，发现节点3的右指针是指向cur的，那么让其指向null，树被调整回如图3-9所示的样子，然后根据标准，cur向右移动来到节点6。

7．cur来到节点6，cur此时有左子树，找到cur的左子树最右节点，即节点5，发现节点5的右指针是指向null的，那么让其指向cur，树被调整成如图3-12所示的样子，然后根据标准，cur向左移动来到节点5。

8．cur来到节点5，cur此时没有左子树，根据标准令cur向右指针方向移动，所以cur回到了节点6。

9．cur来到节点6，cur此时有左子树，找到cur的左子树最右节点，即节点5，发现节点5的右指针是指向cur的，那么让其指向null，树被调整回如图3-9所示的样子，然后根据标准，cur向右移动来到节点7。

10．cur来到节点7，cur此时没有左子树，根据标准令cur向右指针方向移动，cur来到null的位置。

11．cur为空，过程停止。

以上所有步骤都严格按照我们之前说的cur移动标准，cur依次到达的节点为：4、2、1、2、3、4、6、5、6、7，我们将这个序列叫Morris序。

可以看出，在一棵二叉树中，对于有左子树的节点都可以到达两次（4、2、6），对于没有左子树的节点都只会到达一次。对于任何一个只能到达一次的节点X，接下来cur要么跑到X的右子树上，要么就返回上级。而对于任何一个能够到达两次的节点Y，在第一次达到Y之后，cur都会先去Y的左子树转一圈，然后会第二次来到Y，接下来cur要么跑到Y的右子树上，要么就返回上级。同时，对于任何一个能够到达两次的节点Y，是如何知道此时的cur是第一次来到Y还是第二次来到Y呢？如果Y的左子树上的最右节点的指针（mostRight.right）是指向null的，那么此时cur就是第一次到达Y；如果mostRight.right是指向Y的，那么此时cur就是第二次到达Y。这就是Morris遍历和Morris序的实质。全部过程请看如下的morris方法，目前讲到的全部过程都没有出现先序、中序和后序的事情，请读者先理解Morris遍历和Morris序，因为可以根据Morris序进一步加工出先序、中序和后序。

	public void morris(Node head) {
		if (head == null) {
			return;
		}
		Node cur = head;
		Node mostRight = null;
		while (cur != null) {
		    mostRight = cur.left;
		    if (mostRight != null) { // 如果当前cur有左子树
			// 找到cur左子树上最右的节点
			while (mostRight.right != null && mostRight.right != cur) {
				mostRight = mostRight.right;
			}
			// 从上面的while里出来后，mostRight就是cur左子树上最右的节点
			if (mostRight.right == null) { // 如果mostRight.right指向null
				mostRight.right = cur; // 让其指向cur
				cur = cur.left; // cur向左移动
				continue; // 回到最外层的while，继续判断cur的情况
			} else { // 如果mostRight.right是指向cur的
				mostRight.right = null; // 让其指向null
			}
		    }
		    // cur如果没有左子树，cur向右移动
		    // 或者cur左子树上最右节点的右指针是指向cur的，cur向右移动
		    cur = cur.right;
		}
	}

以上代码只使用了有限几个变量，额外空间复杂度肯定是O(1)。但是相信读者已经注意到了，每次来到一个有左子树的节点时，都要去遍历这个节点左子树的右边界，那么时间复杂度还是O(N)吗？依然是。下面给出简单的证明，请看图3-13。

根据Morris遍历的过程，所有需要遍历的右边界如下：

到达节点1两次，每次遍历其左子树的右边界：2 -> 5 -> 11

到达节点2两次，每次遍历其左子树的右边界：4 -> 9

到达节点3两次，每次遍历其左子树的右边界：6 -> 13

到达节点4两次，每次遍历其左子树的右边界：8

到达节点5两次，每次遍历其左子树的右边界：10

到达节点6两次，每次遍历其左子树的右边界：12

到达节点7两次，每次遍历其左子树的右边界：14

可以看出，所有右边界的所有节点数量为O(N)，每条右边界都遍历两次，那么遍历所有节点左子树右边界的总代价为O(N)。因此，Morris遍历的时间复杂度还是O(N)。

根据Morris遍历，加工出先序遍历。

1．对于cur只能到达一次的节点（无左子树的节点），cur到达时直接打印。

2．对于cur可以到达两次的节点（有左子树的节点），cur第一次到达时打印，第二次到达时不打印。

根据Morris遍历，加工出中序遍历。

1．对于cur只能到达一次的节点（无左子树的节点），cur到达时直接打印。

2．对于cur可以到达两次的节点（有左子树的节点），cur第一次到达时不打印，第二次到达时打印。

比如，展示流程中cur依次达到的顺序（Morris序）为：4、2、1、2、3、4、6、5、6、7。

根据加工出先序遍历的规则，将依次打印：4、2、1、3、6、5、7，这就是先序遍历。

根据加工出先序遍历的规则，将依次打印：1、2、3、4、5、6、7，这就是中序遍历。

先序遍历的代码请看如下的morrisPre方法，morrisPre方法就是morris方法的简单改写。

	public void morrisPre(Node head) {
		if (head == null) {
			return;
		}
		Node cur = head;
		Node mostRight = null;
		while (cur != null) {
			mostRight = cur.left;
			if (mostRight != null) {
			    while (mostRight.right != null && mostRight.right != cur) {
				mostRight = mostRight.right;
			    }
			    if (mostRight.right == null) {
				mostRight.right = cur;
				System.out.print(cur.value + " "); // 打印行为
				cur = cur.left;
				continue;
			    } else {
				mostRight.right = null;
			    }
			} else {
			    System.out.print(cur.value + " "); // 打印行为
			}
			cur = cur.right;
		}
		System.out.println();
	}

中序遍历的代码请看如下的morrisIn方法，morrisIn方法也是morris方法的简单改写。

	public void morrisIn(Node head) {
		if (head == null) {
			return;
		}
		Node cur = head;
		Node mostRight = null;
		while (cur != null) {
			mostRight = cur.left;
			if (mostRight != null) {
			    while (mostRight.right != null && mostRight.right != cur) {
				mostRight = mostRight.right;
			    }
			    if (mostRight.right == null) {
				mostRight.right = cur;
				cur = cur.left;
				continue;
			    } else {
				mostRight.right = null;
			    }
			}
			System.out.print(cur.value + " "); // 打印行为
			cur = cur.right;
		}
		System.out.println();
	}

Morris后序遍历的实现，其实也是Morris遍历的改写，但包含稍微复杂的调整过程。

根据Morris遍历，加工出后序遍历。

1．对于cur只能到达一次的节点（无左子树的节点），直接跳过，没有打印行为。

2．对于cur可以到达两次的任何一个节点（有左子树的节点）X，cur第一次到达X时没有打印行为；当第二次到达X时，逆序打印X左子树的右边界。

3．cur遍历完成后，逆序打印整棵树的右边界。

以图3-9来举例说明后序遍历的打印过程，这棵二叉树的Morris序为：4、2、1、2、3、4、6、5、6、7。

当第二次达到2时，逆序打印节点2左子树的右边界：1

当第二次达到4时，逆序打印节点4左子树的右边界：3、2

当第二次达到6时，逆序打印节点6左子树的右边界：5

cur遍历完成后，逆序打印整棵树的右边界：7、6、4

可以看到这个顺序就是后序遍历的顺序。但是我们应该如何实现逆序打印一棵树的右边界？因为整个过程的额外空间复杂度要求是O(1)，所以逆序打印一棵树右边界的过程中，是不能申请额外的数据结构的。为了更好地说明整个过程，下面举一个右边界比较长的例子，如图3-14所示。

假设cur第二次到达了A，并且要逆序打印节点A左子树的右边界，首先将E.R指向null，然后将右边界逆序调整成如图3-15所示的样子，整个过程类似单链表的逆序操作。

这样我们就可以从节点E开始，依次通过每个节点的right指针逆序打印整个左边界。在打印完B后，把右边界再逆序一次，调回来即可。Morris后序遍历的具体实现请参看如下代码中的morrisPos方法。

 

	public void morrisPos(Node head) {
		if (head == null) {
			return;
		}
		Node cur = head; Node mostRight = null;
		while (cur != null) {
			mostRight = cur.left;
			if (mostRight != null) {
			    while (mostRight.right != null && mostRight.right != cur) {
				mostRight = mostRight.right;
			    }
			    if (mostRight.right == null) {
				mostRight.right = cur;
				cur = cur.left;
				continue;
			    } else {
				mostRight.right = null;
				printEdge(cur.left);
			    }
			}
			cur = cur.right;
		}
		printEdge(head);
		System.out.println();
	}

	public static void printEdge(Node head) {
		Node tail = reverseEdge(head);
		Node cur = tail;
		while (cur != null) {
			System.out.print(cur.value + " ");
			cur = cur.right;
		}
		reverseEdge(tail);
	}

	public static Node reverseEdge(Node from) {
		Node pre = null;
		Node next = null;
		while (from != null) {
			next = from.right;
			from.right = pre;
			pre = from; from = next;
		}
		return pre;
	}