07-二叉树的基本算法
二叉树结构
结构描述：
Class Node {
V value;
Node left;
Node right;
}
二叉树的先序、中序、后序遍历
先序：任何子树的处理顺序都是，先头节点、再左子树、然后右子树
中序：任何子树的处理顺序都是，先左子树、再头节点、然后右子树
后序：任何子树的处理顺序都是，先左子树、再右子树、然后头节点
递归方式实现二叉树的先序、中序、后序遍历
1.理解递归序
递归序：在整个过程中，每一个节点都会到达3次。
2.先序、中序、后序都可以在递归序的基础上加工出来。
3.第一次到达一个节点就打印就是先序、第二次打印即中序、第三次即后序
先序代码
public static void pre(Node head) {
if (head == null) {
return;
}
System.out.println(head.value);
pre(head.left);
pre(head.right);
}
中序代码
public static void in(Node head) {
if (head == null) {
return;
}
in(head.left);
System.out.println(head.value);
in(head.right);
}
后序代码
public static void pos(Node head) {
if (head == null) {
return;
}
pos(head.left);
pos(head.right);
System.out.println(head.value);
}
非递归方式实现二叉树的先序、中序、后序遍历
1.任何递归函数都可以改成非递归
2.自己设计压栈的来实现
如果不用递归实现，我们就需要栈结构，来自己压栈实现。
非递归先序
先序是头、左、右的一个顺序。
具体步骤为，先将根节点压入栈。
然后重复下面三个步骤：
1.弹出栈节点，并打印
2.刚才弹出栈的节点，如果有右子节点，压入右子节点
3.如果有左子节点，再压入左子节点
回到步骤1，继续（即while循环，终止条件栈为空)
这样得到的顺序是 头 左 右 先序遍历
public static void pre(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.弹出栈节点，并压入准备倒序的栈。
2.刚才弹出栈的节点，如果有左子节点，压入左子节点
3.如果有右子节点，再压入右子节点
回到步骤1，继续（即while循环，终止条件栈为空)
循环完成后，我们将倒序栈中的节点一一弹出打印，非递归后序。
public static void pos1(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();
}
非递归中序
在非递归的中序遍历，我们可以用左边界的视角，来看待整棵树。
如ABDHP是A为根节点的树的左边界，Q可以看做Q为根节点的树的左边界，
EJ可以看做E为根节点的树的左边界。
我们可以用左边界将整棵树割分。
因为中序遍历为，左、头、右，且在右的时候可以看做右的左头。
所有我们不断分解，分解完左后，会去分解右的左
代码如下
public static void in(Node cur) {
System.out.print("in-order: ");
if (cur != null) {
Stack<Node> stack = new Stack<Node>();
while (!stack.isEmpty() || cur != null) {
if (cur != null) {
stack.push(cur);
cur = cur.left;
} else {
cur = stack.pop();
System.out.print(cur.value + " ");
cur = cur.right;
}
}
}
System.out.println();
}
代码流程为，先将整棵树的左边不断压栈。ABDHP压入栈中，因为是先压栈，然后跳到下一个left。
但P.left为空，会进入else：弹出栈节点P，打印P，并跳到P.right
但P.right也为空，会进入else：会弹出栈节点H，打印H，并跳到Q
Q节点不为空，会执行压栈操作，上面讲了我们会以左边界来分割，所有会将以Q为根节点的树的左边界压入栈，但Q只有一个，Q.left和Q.right为空。
Q.left为空，进入else，弹出Q，打印，跳到Q.right
Q.right为空，进入else，弹出D，打印，跳到F。
打印顺序为PHQDFB
所以我们看到以上就是中序遍历。
当B打印后我们会从E开始，分割左边界，EJ，找到 J ，然后和上面一样一直执行。
所以宏观上，是以左边界来划分的，
非递归后序遍历优化
在上面的后序遍历中，我们改写了先序遍历，并用另一个栈倒序输出，来实现后序遍历。
一共使用了2个栈。
但有更好的方法，可以有更低的空间复杂度。
循环中，if/else有着3个逻辑分支。
分支1：如果左右子节点没有操作过，会将左子节点压入栈
分支2：如果右子节点没有操作过，将右子节点压入栈
我们怎么区分有没有操作打印过子节点
分支3中：弹出打印后，h会跟踪打印的节点。
所以我们在分支1、2中可以用h来判断是否进行过了打印
public static void pos2(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();
}
实现二叉树的按层遍历
1.其实就是宽度优先遍历，用队列
2.可以通过设置flag变量的方式，来发现某一层的结束（看题目）
二叉树的按层遍历，主要用队列实现。
将根节点进入队列。
然后开始while循环，队列空停止。
队列出队一个cur节点，打印。
cur节点左子节点不为空，进队列。
cur节点右子节点不为空，进队列。
其实就是，在队列中，同层节点是相邻的。而每次出队列打印，都会将自己左右子节点进队列，这样子节点进入完后，也是相邻的。
public static void level(Node head) {
if (head == null) {
return;
}
Queue<Node> queue = new LinkedList<>();
queue.add(head);
while (!queue.isEmpty()) {
Node cur = queue.poll();
System.out.println(cur.value);
if (cur.left != null) {
queue.add(cur.left);
}
if (cur.right != null) {
queue.add(cur.right);
}
}
}
二叉树的序列化和反序列化
1）可以用先序或者中序或者后序或者按层遍历，来实现二叉树的序列化
2）用了什么方式序列化，就用什么样的方式反序列化
3）中序遍历无法实现序列化和反序列化
二叉树的序列化主要就是，null也要序列化。因为这样才能准确找到每个节点的位置，以准确还原。
先序遍历的序列化与反序列化
其实就是先序遍历，将节点加入集合，null节点就用null补。
后序，层序这些都如此。
public static Queue<String> preSerial(Node head) {
Queue<String> ans = new LinkedList<>();
pres(head, ans);
return ans;
}
public static void pres(Node head, Queue<String> ans) {
if (head == null) {
ans.add(null);
} else {
ans.add(String.valueOf(head.value));
pres(head.left, ans);
pres(head.right, ans);
}
}
public static Node buildByPreQueue(Queue<String> prelist) {
if (prelist == null || prelist.size() == 0) {
return null;
}
return preb(prelist);
}
public static Node preb(Queue<String> prelist) {
String value = prelist.poll();
if (value == null) {
return null;
}
Node head = new Node(Integer.valueOf(value));
head.left = preb(prelist);
head.right = preb(prelist);
return head;
}
还剩几题，就不写题解了
二叉树的最大宽度
如何设计一个打印整棵树的打印函数
返回后继节点
二叉树结构如下定义：
class Node {
public int value;
public Node left;
public Node right;
public Node parent;
}
给你二叉树中的某个节点，返回该节点的后继节点
后继节点：二叉树中，中序遍历里该节点的后一个节点
暴力解法：到根节点，中序遍历。O(N)
找前驱节点也类似
从上到下打印对折纸条所有折痕的方向
请把一段纸条竖着放在桌子上，然后从纸条的下边向上方对折1次，压出折痕后展开。此时折痕是凹下去的，即折痕突起的方向指向纸条的背面。 如果从纸条的下边向上方连续对折2次，压出折痕后展开，此时有三条折痕，从上到下依次是下折痕、下折痕和上折痕。
给定一个输入参数N，代表纸条都从下边向上方连续对折N次。 请从上到下打印所有折痕的方向。
例如:N=1时，打印: down N=2时，打印: down down up