5、求树的最大宽度6、折纸问题（二叉树思想启蒙）7、判断一颗树是不是完全二叉树8、多叉树与二叉树的互换(需要理解递归过程)
8.1 多叉树转二叉树8.2 二叉树转多叉树 9、给定一个二叉树节点，其中节点指针还包括它的父指针，寻找它中序遍历情况下的下一个节点10、证明先序遍历x的左边和后序遍历x的右边的交集仅仅是x的祖先节点
5、求树的最大宽度思路：在层序遍历的基础上，多用三个变量，一个记录当前层的最后一个位置，一个记录下一层的最后一个位置，一个记录当前层的宽度，这样每层的结束时机遍历完都知道。每次遍历一层更新迭代即可。为什么需要当前层 和 下一层的最后一个位置都需要记录。因为每次当前层来到最后一个位置时，就可以知道下一层应该开始了，那么宽度就可以重新设置。同时也可以更新下一层的结束位置。
package tree;
import java.util.linkedList;
import java.util.Queue;
public class Code05_MaxWidth {
public static int maxWidth(TreeNode root){
if (root == null){
return 0;
}
Queue queue = new linkedList<>();
TreeNode cur = root;
TreeNode curEnd = root;
TreeNode nextEnd = root;
int count = 0;
int width = 1;
queue.add(cur);
while (!queue.isEmpty()){
cur = queue.poll();
count++;
if (cur.left != null){
//每次都更新nextend，那么当cur来到curend时，nexrend会被正确更新
queue.add(cur.left);
nextEnd = cur.left;
}
if(cur.right != null){
queue.add(cur.right);
nextEnd = curEnd.right;
}
if(cur == curEnd){
width = Math.max(width,count);
count = 0;
curEnd = nextEnd;
}
}
return width;
}
}
6、折纸问题（二叉树思想启蒙）
把一段纸条竖着放在桌子上，然后从纸条的下边向上方对折1次，压出折痕后展开。此时 折痕是凹下去的，即折痕突起的方向指向纸条的背面。如果从纸条的下边向上方连续对折2 次，压出折痕后展开，此时有三条折痕，从上到下依次是下折痕、下折痕和上折痕。给定一 个输入参数N，代表纸条都从下边向上方连续对折N次，请从上到下打印所有折痕的方向 例如：N=1时，打印： down；N=2时，打印： down down up将每个折痕代表为树种的每一个节点，可以看到根节点为down，然后每一个节点的左孩子为down，右孩子为up，而N即为二叉树的层数，由此可以用二叉树的中序遍历进行打印我们实际不构建二叉树，因为太浪费空间。用一个boolean（isLeft）代表是左孩子还是右孩子。如果是左孩子就打印down，否则打印up。由于根节点打印down，所以第一次递归传入为true。
package tree;
public class Code06_PaperFolding {
public static void printAll(int n){
process(1,n,true);
}
public static void process(int i,int n,boolean isLeft){
if(i > n){
return;
}
process(i + 1, n, true);
System.out.print(isLeft ? "down - " : "up - ");
process(i + 1, n, false);
}
}
7、判断一颗树是不是完全二叉树
完全二叉树：要么每一层都是满的，要么除了最后一层不满且孩子节点依次从左向右，满足这两种情况称为完全二叉树。思路很简单：对二叉树进行层序遍历，不满足完全二叉树只有两种情况。
- 左右孩子不全且后序节点子树不为null左孩子为null但有右孩子
package tree;
import java.util.linkedList;
import java.util.Queue;
public class Code07_IsCBTByLevel {
public static boolean isCBT(TreeNode head) {
if (head == null) {
return true;
}
Queue queue = new linkedList<>();
TreeNode cur = null;
queue.add(head);
boolean childrenLess = false;
while (!queue.isEmpty()) {
cur = queue.poll();
if (
(childrenLess && (cur.left != null || cur.right != null))
|| (cur.left == null && cur.right != null)
) {
return false;
}
if (cur.left != null){
queue.add(cur.left);
}
if(cur.right != null){
queue.add(cur.right);
}
if (cur.right == null || cur.left ==null){
childrenLess = true;
}
}
return true;
}
}
8、多叉树与二叉树的互换(需要理解递归过程)
8.1 多叉树转二叉树
对于每一个节点来说，把它的所有孩子节点依次串在左树的右边界上
public static class MultiwayTree{
public int value;
public ArrayList children;
public MultiwayTree(int value) {
this.value = value;
children = new ArrayList<>();
}
public MultiwayTree(int value, ArrayList children) {
this.value = value;
this.children = children;
}
}
public static TreeNode encode(MultiwayTree multiwayHead){
if (multiwayHead == null){
return null;
}
return en(multiwayHead.children);
}
public static TreeNode en(List children){
TreeNode head = null;
TreeNode cur = null;
for (MultiwayTree child : children){
TreeNode tNode = new TreeNode(child.value);
if (head == null){
head = tNode;
}else {
cur.right = tNode;
}
cur = tNode;
cur.left = en(child.children);
}
return head;
}
8.2 二叉树转多叉树
遍历每个节点左子树的右边界，依次作为该节点的孩子
public static MultiwayTree decode(TreeNode head){
if(head == null){
return null;
}
return new MultiwayTree(head.value,de(head.left));
}
public static List de(TreeNode node){
List children = new ArrayList<>();
while (node != null){
MultiwayTree cur = new MultiwayTree(node.value,de(node.left));
children.add(cur);
node = node.right;
}
return children;
}
9、给定一个二叉树节点，其中节点指针还包括它的父指针，寻找它中序遍历情况下的下一个节点
结合前面二叉树的中序遍历非递归实现可知，如果某个节点有右树，那么它的下一个位置必定为其右子树的最左节点如果它没有右孩子，那么它将会沿着parent指针一直走上去，直到parent为某一个节点的左孩子或者来到根节点，那么下一个位置将会是parent。
package tree;
public class Code09_GetSuccessorNodeWithIn {
public static class Node{
public int value;
public Node left;
public Node right;
public Node parent;
public Node(int value) {
this.value = value;
}
}
public Node getSuccessorNode(Node head){
if (head == null){
return null;
}
Node cur = head;
//右子树不为空
if (cur.right != null){
cur = cur.left;
while (cur.left != null){
cur = cur.left;
}
return cur;
}else {
//右子树为空，找打它的父亲节点，直到父亲节点来到head或者父亲节点为某个节点的左子树
//只有head位置的parent为null，所以parent为null就来到了头结点
Node parent = cur.parent;
while (parent != null && parent.right == cur){
cur = parent;
parent = cur.parent;
}
return parent;
}
}
}
10、证明先序遍历x的左边和后序遍历x的右边的交集仅仅是x的祖先节点
对于x的父节点
先序遍历-： 根---->左---->-右—> x的左边必包括父亲节点
后序遍历-： 左---->右---->-根—> x的右边必包括父亲节点
对于x的孩子节点
先序遍历，x的孩子节点全出现在右边
后序遍历，x的孩子节点全出现在左边
对于x的兄弟节点
先序遍历
x作为左树，兄弟节点全在右边x作为右树，兄弟节点全在左边
后序遍历
x作为左树，兄弟节点全在右边x作为右树，兄弟节点全在左边
对x先序左边和x后序的右边取交集，发现只有父亲节点符合条件
