二叉树系列问题

1，分别用递归和非递归方式实现二叉树的遍历
题目：要求用非递归和递归方式分别按照先序、中序、后序遍历二叉树；约定先序遍历顺序为：根、左、右，中序：左、中、右，后序：左、右、中。
递归方式较为简单，代码如下：

先序：

public static void preOrderRecur(Node head) {
		if (head == null) {
			return;
		}
		System.out.print(head.value + " ");
		preOrderRecur(head.left);
		preOrderRecur(head.right);
}

中序：

public static void inOrderRecur(Node head) {
		if (head == null) {
			return;
		}
		inOrderRecur(head.left);
		System.out.print(head.value + " ");
		inOrderRecur(head.right);
}

后序：

public static void posOrderRecur(Node head) {
		if (head == null) {
			return;
		}
		posOrderRecur(head.left);
		posOrderRecur(head.right);
		System.out.print(head.value + " ");
}

注意：这就是打印的时机不一样，形成了三种遍历方式。
用递归方式解决的问题都能用非递归来解决。这是因为递归函数无非就是利用函数栈来保存信息，如果自己申请的数据结构来代替函数栈，也可以实现相同的功能。
用非递归方式实现先序遍历具体规则如下：
1),申请一个新的栈，记为stack。然后将头节点head压入stack。
2),从stack中弹出栈顶结点，记为cur，然后打印cur的值，再将节点cur的右孩子(不为空的话)先压入stack中，最后将cur的左孩子(不为空的话)压入stack中。
3),不断重复步骤2，直到stack为空，全部过程为结束。

public static void preOrderUnRecur(Node head) {
		System.out.print("pre-order: ");
		if (head != null) {
			Stack<Node> stack = new Stack<Node>();
			stack.add(head);
			while (!stack.isEmpty()) {
				head = stack.pop();
				System.out.print(head.value + " ");
				if (head.right != null) {
					stack.push(head.right);
				}
				if (head.left != null) {
					stack.push(head.left);
				}
			}
		}
		System.out.println();
}

以上是非递归实现先序的代码。
用非递归方式实现中序遍历的规则：
1),申请新的栈，记为stack，初始时，令变量cur=head。
2),先把cur节点压入栈中，对以cur为头的整颗子树来说，依次把左边界压入栈中，即不停地令cur=cur.left，然后重复步骤2。
3),不断重复步骤2，直到cur为空，此时从stack中弹出一个节点，记为node，打印node的值，并且让cur=node.right，然后继续重复步骤2.
4),当stack为空且cur为空时，整个过程停止

public static void inOrderUnRecur(Node head) {
		System.out.print("in-order: ");
		if (head != null) {
			Stack<Node> stack = new Stack<Node>();
			while (!stack.isEmpty() || head != null) {
				if (head != null) {
					stack.push(head);
					head = head.left;
				} else {
					head = stack.pop();
					System.out.print(head.value + " ");
					head = head.right;
				}
			}
		}
		System.out.println();
}

以非递归方式实现后序遍历的规则：
代码：

public static void posOrderUnRecur1(Node head) {
    System.out.print("pos-order: ");
    if (head != null) {
        Stack<Node> s1 = new Stack<Node>();
        Stack<Node> s2 = new Stack<Node>();
        s1.push(head);
        while (!s1.isEmpty()) {
            head = s1.pop();
            s2.push(head);
            if (head.left != null) {
                s1.push(head.left);
            }
            if (head.right != null) {
               s1.push(head.right);
            }
        }
        while (!s2.isEmpty()) {
            System.out.print(s2.pop().value + " ");
        }
    }
    System.out.println();
}

方法二非递归实现后序遍历，只使用一个栈。

public static void posOrderUnRecur2(Node h) {
		System.out.print("pos-order: ");
		if (h != null) {
			Stack<Node> stack = new Stack<Node>();
			stack.push(h);
			Node c = null;
			while (!stack.isEmpty()) {
				c = stack.peek();
				if (c.left != null && h != c.left && h != c.right) {
					stack.push(c.left);
				} else if (c.right != null && h != c.right) {
					stack.push(c.right);
				} else {
					System.out.print(stack.pop().value + " ");
					h = c;
				}
			}
		}
		System.out.println();
}

2，打印二叉树的边界节点
题目：给定一棵二叉树的头节点，按照如下两种标准分别实现二叉树边界节点的逆时针打印。
标准一：
1，头节点为边界节点。
2，叶节点为边界节点。
3，如果节点在其所在的层中是最左或最右的，那么也是边界节点。
标准二：
1，头节点为边界节点
2，叶节点为边界节点
3，树左边界延伸下去的路径为边界节点
4，树右边界延伸下去的路径为边界节点
按照标准一打印的全部过程：

public static void printEdge1(Node head) {
		if (head == null) {
			return;
		}
		int height = getHeight(head, 0);
		Node[][] edgeMap = new Node[height][2];
		setEdgeMap(head, 0, edgeMap);
		// print left edge
		for (int i = 0; i != edgeMap.length; i++) {
			System.out.print(edgeMap[i][0].value + " ");
		}
		// print leaf node but not in map
		printLeafNotInMap(head, 0, edgeMap);
		// print right edge but not left edge
		for (int i = edgeMap.length - 1; i != -1; i--) {
			if (edgeMap[i][0] != edgeMap[i][1]) {
				System.out.print(edgeMap[i][1].value + " ");
			}
		}
		System.out.println();
}
public static int getHeight(Node h, int l) {
		if (h == null) {
			return l;
		}
		return Math.max(getHeight(h.left, l + 1), getHeight(h.right, l + 1));
	}

	public static void setEdgeMap(Node h, int l, Node[][] edgeMap) {
		if (h == null) {
			return;
		}
		edgeMap[l][0] = edgeMap[l][0] == null ? h : edgeMap[l][0];
		edgeMap[l][1] = h;
		setEdgeMap(h.left, l + 1, edgeMap);
		setEdgeMap(h.right, l + 1, edgeMap);
	}

	public static void printLeafNotInMap(Node h, int l, Node[][] m) {
		if (h == null) {
			return;
		}
		if (h.left == null && h.right == null && h != m[l][0] && h != m[l][1]) {
			System.out.print(h.value + " ");
		}
		printLeafNotInMap(h.left, l + 1, m);
		printLeafNotInMap(h.right, l + 1, m);
}

按照标准二的要求实现打印的具体过程如下：

public static void printEdge2(Node head) {
		if (head == null) {
			return;
		}
		System.out.print(head.value + " ");
		if (head.left != null && head.right != null) {
			printLeftEdge(head.left, true);
			printRightEdge(head.right, true);
		} else {
			printEdge2(head.left != null ? head.left : head.right);
		}
		System.out.println();
	}

	public static void printLeftEdge(Node h, boolean print) {
		if (h == null) {
			return;
		}
		if (print || (h.left == null && h.right == null)) {
			System.out.print(h.value + " ");
		}
		printLeftEdge(h.left, print);
		printLeftEdge(h.right, print && h.left == null ? true : false);
	}

	public static void printRightEdge(Node h, boolean print) {
		if (h == null) {
			return;
		}
		printRightEdge(h.left, print && h.right == null ? true : false);
		printRightEdge(h.right, print);
		if (print || (h.left == null && h.right == null)) {
			System.out.print(h.value + " ");
		}
}

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

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

	public static 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 static String getSpace(int num) {
		String space = " ";
		StringBuffer buf = new StringBuffer("");
		for (int i = 0; i < num; i++) {
			buf.append(space);
		}
		return buf.toString();
}

4，二叉树的序列化和反序列化
题目：二叉树被记录成文件的过程叫做二叉树的序列化，通过文件重建成原来的二叉树的过程叫做二叉树的反序列化。给定一颗二叉树的头节点hed，并已知二叉树节点值得类型为32位整型，请设计一种二叉树序列化和反序列化的方案，并用代码实现。
思路：
方法一：先介绍下先序遍历下的序列化过程，首先假设序列化的结果字符串为str，初始时str=””。先序遍历二叉树，如果遇到null节点，就在字符串末尾加上”#!”，”#”表示这个节点为空，节点值不存在，”!”表示一个值的结束；如果遇到不为空的节点，假设节点值为3，就在str的末尾加上”3!”。
代码如下：

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

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

public static 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[0…4]建立节点12的左子树，
2，遇到”3”，生成节点值为3的节点，它是节点12的左孩子，然后用values[2…4]建立节点3的左子树。
3，”#”，生成null节点，它是节点3的左孩子，该节点为null，所以这个节点没有后续建立子树的过程。回到节点3后，继续用values[3…4]建立节点3的右子树。
4，后续过程就是依次。
先序遍历反序列化的全部过程代码如下：

   public static 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 static 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为空，然后实现二叉树的按层遍历，具体方式是利用队列结构，这也是宽度遍历图的常见方式。
代码：

  public static 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;
  }

5，遍历二叉树的神级方法–Morris方法
题目：给定一个二叉树的head，完成先序、中序、后续遍历。要求时间复杂度为O(n)，额外空间复杂度为O(1)。
思路：难度在于复杂度的要求，尤其是额外空间复杂度为O(1)的要求。之前的遍历方法虽然常用但无法做到额外空间复杂度为O(1)。这是因为遍历二叉树的递归方法实际上利用了函数栈(系统帮压栈)，非递归的方法使用了申请的栈，两者的额外空间复杂度都与树的高度有关，所以空间复杂度为O(h)，h为树的高度。那么完全不用栈结构能完成三种遍历吗？可以，答案是使用二叉树节点中大量指向null的指针，本提就是大名鼎鼎的Morris遍历，由Joseph Morris于1979年发明。
中序代码如下：

  public static void morrisIn(Node head) {
if (head == null) {
	return;
}
Node cur1 = head;
Node cur2 = null;
while (cur1 != null) {
	cur2 = cur1.left;
	if (cur2 != null) {
		while (cur2.right != null && cur2.right != cur1) {
			cur2 = cur2.right;
		}
		if (cur2.right == null) {
			cur2.right = cur1;
			cur1 = cur1.left;
			continue;
		} else {
			cur2.right = null;
		}
	}
	System.out.print(cur1.value + " ");
	cur1 = cur1.right;
}
System.out.println();
  }

先序遍历代码：

  public static void morrisPre(Node head) {
if (head == null) {
	return;
}
Node cur1 = head;
Node cur2 = null;
while (cur1 != null) {
	cur2 = cur1.left;
	if (cur2 != null) {
		while (cur2.right != null && cur2.right != cur1) {
			cur2 = cur2.right;
		}
		if (cur2.right == null) {
			cur2.right = cur1;
			System.out.print(cur1.value + " ");
			cur1 = cur1.left;
			continue;
		} else {
			cur2.right = null;
		}
	} else {
		System.out.print(cur1.value + " ");
	}
	cur1 = cur1.right;
}
System.out.println();
  }

后续遍历代码：

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

6，在二叉树中找到累加和为指定值得最长路径长度
题目：给定一颗二叉树头节点head和一个32位整数sum，二叉树节点值类型为整型，求累加和为sum的最长路径长度。路径是指从某个节点往下，每次最多选择一个孩子节点或者不选所形成的节点链。
7，找到二叉树中的最多搜索二叉子树
题目：给定一颗二叉树的头节点head，已知所有节点值都不一样，找到含有节点最多的搜索二叉子树，并返回这棵子树的头节点。
要求：如果节点数为n，要求时间复杂度为O(n)，额外空间复杂度为O(h)，h为二叉树高度。
思路：
以节点node为头的树中，最大的搜索二叉树只能来自于以下两种情况。
第一种：如果来自node左子树上的最大搜索二叉子树是以node.left为头的；来自node右子树上的最大搜索二叉子树是以node.left为头的，node左子树上的最大搜索二叉子树的最大值小于node.value；node右子树上的最大搜索二叉子树的最小值大于node.value，那么以节点node为头的整棵树都是二叉搜索树。
第二种：如果不满足第一种，说明以节点node为头的树整体不能连成搜索二叉树。这种情况下，以node为头的树的最大搜索二叉树是来自于node的左子树上的最大搜索二叉子树和来自于node右子树上的最大搜索二叉子树之间，节点数较多的那个。
求解的具体步骤：
1，整体过程是二叉树的后续遍历
2，遍历到当前节点记为cur时，先遍历cur的左子树收集4个信息，分别是左子树上最大搜索二叉子树的头节点(IBST)、节点数(ISize)、最小值(IMin)、和最大值(IMax)。再遍历cur的右子树收集4个信息，分别是右子树上最大搜索二叉子树的头节点(rBST)、节点数(rSize)、最小值(rMin)和最大值(rMax)。
3，根据步骤2所收集的信息，判断是否满足第一种情况，如果满足第一种情况，就返回cur节点，如果满足第二种，就返回lBST和rBST中较大的一个。
4，可以使用全局变量的方式实现步骤2中收集节点数、最小值和最大值的问题。找到最大搜索二叉子树的具体过程参看下面代码中的biggestSubBST。

   public static Node biggestSubBST(Node head) {
	int[] record = new int[3]; // 0->size, 1->min, 2->max
	return posOrder(head, record);
}

public static Node posOrder(Node head, int[] record) {
	if (head == null) {
		record[0] = 0;
		record[1] = Integer.MAX_VALUE;
		record[2] = Integer.MIN_VALUE;
		return null;
	}
	int value = head.value;
	Node left = head.left;
	Node right = head.right;
	Node lBST = posOrder(left, record);
	int lSize = record[0];
	int lMin = record[1];
	int lMax = record[2];
	Node rBST = posOrder(right, record);
	int rSize = record[0];
	int rMin = record[1];
	int rMax = record[2];
	record[1] = Math.min(lMin, value);
	record[2] = Math.max(rMax, value);
	if (left == lBST && right == rBST && lMax < value && value < rMin) {
		record[0] = lSize + rSize + 1;
		return head;
	}
	record[0] = Math.max(lSize, rSize);
	return lSize > rSize ? lBST : rBST;
   }

8，找到二叉树中符合搜索二叉树条件的最大拓扑结构
题目：给定一棵二叉树头节点head，已知所有节点的值都不一样，返回其中最大的且符合搜索二叉树条件的最大拓扑结构的大小。

9，二叉树的按层打印与ZigZag打印
题目：给定一颗二叉树的头节点head，分别实现按层打印和zigzag打印二叉树的函数。例如：头节点1，左孩子2，右孩子为3，节点2左孩子为4，右孩子为空，节点3左孩子为5，右孩子为6，节点5左孩子为7，节点5右孩子为8。
按层打印时，输出格式如下：
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 1 from right to left：3 2
level 1 from left to right：4 5 6
level 1 from right to left：8 7
二叉树按层打印的代码：

  public static 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();
  }

思路：按层打印对二叉树做简单的宽度优先遍历即可，但本题有额外的要求，就是同一层的节点必须打印在一行上，并且要输出行号。这就需要在原来的宽度优先遍历做一些改进。关键是如何换行。
只需用两个node型的变量last和nLast即可，last表示当前打印行的最右节点，nLast表示下一行的最右节点，假设我们每一层都做从左到右的宽度优先遍历，如果发现遍历到的节点等于last，说明该换行了。换行之后只要令last=nLast，就可以继续下一行的打印过程，此过程重复，直到所有的节点都打印完。那么问题就变成了如何更新nLast？只需要让nLast一直跟踪记录宽度优先遍历队列中的最新加入的节点即可。这是因为最新加入队列的节点一定是目前已经发现的下一行的最右节点。所以在当前行打印完时，nLast一定是下一行所有节点中的最右节点。
2)二叉树zigzag打印
先介绍不推荐的做法：
使用arraylist结构，两个，分别记为list1.list2，用list1去收集当前层的节点，然后从左到右打印当前层，接着把当前层的孩子节点放进list2，并从右到左打印，接下来再把list2的所有的节点的孩子节点放入list1，如此反复。不推荐的原因是arraylist是动态数组，在这个结构中，当元素达到一定的量时，会发生扩容操作，扩容操作的时间复杂度是O(n)比较高的，这个结构增加删除元素的时间复杂度都比较高。总之，用这种数据结构不够干净和纯粹，最好不要使用。
推荐的方法是双端队列，具体为java的LinkedList结构，这个结构的底层是非常纯粹的双端队列结构，本书的方法也仅使用双端队列结构的基本操作。
先举题目的例子来展示大体过程，首先生成双端队列结构dp，将节点1从dp的头部放入dp。
原则1：如果是从左到右的过程，那么一律从dp的头部弹出节点，如果弹出的节点没有孩子节点，当然不用放入任何节点到dp中；如果当前节点有孩子节点，先让左孩子从尾部进入dp，再让右孩子从尾部进入dp。
根据原则1，先从dp头部弹出节点1并打印，然后先让节点2从dp尾部进入，再让节点3从dp尾部进入。
原则2：如果是从右到左的过程，那么一律从dp的尾部弹出节点，如果弹出的节点没有还节点，当然不能放入任何节点到dp中；如果当前节点有孩子节点，先让右孩子从头部进入dp，再让左孩子从头部进入dp。
根据原则2，先从dp尾部弹出节点3并打印，然后先让节点6从dp头部进入，再让节点5从dp头部进入。
根据原则2，先从dp尾部弹出节点并打印，然后让节点4从dp头部进入。
根据原则1，依次从dp头部弹出节点4、5、6并打印，这期间先让节点7从dp尾部进入，再让节点8从dp尾部进入。
最后根据原则2，依次从dp尾部弹出节点8和节点7并打印即可。
用原则1和2的过程切换，我们可以完成zigzag的打印过程，所以问题在于，如何确定原则1和原则2的切换时机，其实还是如何确定每一层最后一个节点的问题。

  public static 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);
printLevelAndOrientation(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();
		printLevelAndOrientation(level++, lr);
	}
}
System.out.println();
  }