一、统计二叉树的最大宽度（按层遍历）

1、使用map

	//求一个二叉树的最大宽度
	//Map集合记录二叉树中每一个节点对应的层数（已知+迭代）
	//用一个变量记录当前层数curLevel
	//用max记录当前最大节点数，不断在更新
	//用curLevelNodes记录当前层的当前结点数
	public static int getLength(Node head) {
		if(head == null) {
			return 0;
		}
		HashMap<Node,Integer> map = new HashMap<>();
		//最终需要返回的结果
		int max = 0;
		int curLevelNodes = 0;
		int curLevel = 1;//一进去就是在数第一层树的结点数
		map.put(head, 1);
		Queue<Node> queue = new LinkedList<>();
		//将根节点放入队列
		queue.add(head);
		while(!queue.isEmpty()) {//不为空
			//弹出队头节点
			Node curNode = queue.poll();
			//得到弹出的节点的层数
			int curNodeLevel = map.get(curNode);//1
			if(curNode.left != null) {
				//加入Map集合
				map.put(curNode.left, curNodeLevel+1);
				queue.add(curNode.left);
			}
			if(curNode.right != null) {
				//加入Map集合
				map.put(curNode.right, curNodeLevel+1);
				queue.add(curNode.right);
			}
			if(curNodeLevel == curLevel) {//在数第1层 == 节点属于第1层
				curLevelNodes ++;
			}else {//发现当前节点已经属于下一层了
				//得到直到上一层的最大结点数
				max = Math.max(max, curLevelNodes);
				curLevelNodes = 1;
				curLevel ++;
			}
		}
		max = Math.max(max, curLevelNodes);
		return max;
	}

2、不使用map

	public static int getLength2(Node head) {
		if(head == null) {
			return 0;
		}
		int max = 0;
		Node curEnd = head;
		Node nextEnd = null;
		int curLevelNodes = 0;
		
		Queue<Node> queue = new LinkedList<>();
		queue.add(head);
		
		while(!queue.isEmpty()) {
			Node curNode = queue.poll();
			System.out.println(curNode.val);
			if(curNode.left != null) {
				nextEnd = curNode.left;
				queue.add(curNode.left);
			}
			if(curNode.right != null) {
				nextEnd = curNode.right;
				queue.add(curNode.right);
			}
			curLevelNodes++;
			if(curNode == curEnd) {
				curEnd = nextEnd;
				max = Math.max(max, curLevelNodes);
				curLevelNodes = 0;
			}
		}
		return max;
	}

二、序列化与反序列化

最主要的是空值也需要算入

1、按层

序列化：

public static Queue<String> levelSerial(Node head){
	Queue<String> ans = new LinkedList<>();
	if(head == null) {
		ans.add(null);
	}else {
		ans.add(String.valueOf(head.val));
		Queue<Node> queue = new LinkedList<>();
		queue.add(head);
		while(!queue.isEmpty()) {
			Node node = queue.poll();
			if(node.left != null) {
				ans.add(String.valueOf(node.left.val));
				queue.add(node.left);
			}else {
				ans.add(null);
			}
			
			if(node.right != null) {
				ans.add(String.valueOf(node.right.val));
				queue.add(node.right);
			}else {
				ans.add(null);
			}
		}
	}
	return ans;
}

反序列化：

	public static Node bulidByLevelQueue(Queue<String> levelList) {
		if(levelList == null || levelList.size() == 0) {
			return null;
		}
		Queue<Node> queue = new LinkedList<>();
		//构造根节点，有可能为空
		Node head = generateNode(levelList.poll());
		//head有可能返回空
		if(head != null) {
			queue.add(head);
		}
		Node node = null;
		while(!queue.isEmpty()) {//如果根节点为空，根本进不来
			node = queue.poll();
			node.left = generateNode(levelList.poll());
			node.right = generateNode(levelList.poll());
			if(node.left != null) {
				queue.add(node.left);//如果是非空结点，加入队列才能为它赋值左右孩子
			}
			if(node.right != null) {
				queue.add(node.right);
			}
		}
		return head;
	}
	
	//从队列中取字符串，封装成结点，如果是null，返回空节点
	public static Node generateNode(String val) {
		if(val == null) {
			return null;
		}
		return new Node(Integer.valueOf(val));
	}

2、先/中/后

以先序为例：
序列化，将结果放入到队列中

	public static Queue<String> preSerial(Node head){
		Queue<String> queue = new LinkedList<>();
		pres(head,queue);
		return queue;
	}
	public static void pres(Node head,Queue<String> queue) {
		if(head == null) {
			queue.add(null);
		}else {
			queue.add(String.valueOf(head.val));
			pres(head.left,queue);
			pres(head.right,queue);
		}
	}

反序列化：

	//返回头节点
	public static Node buildByPreQueue(Queue<String> prelist) {
		//这里的Node是要返回的根节点
		if(prelist == null || prelist.size() == 0) {
			return null;
		}
		return preb(prelist);//递归函数
	}
	//不需要对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.right = preb(prelist);
		head.left = preb(prelist);
		return head;
	}

三、打印二叉树（右中左）

	/**
	 * 先解决主要矛盾，不然无法推进整个算法
	 * 主要矛盾即算法的框架，次要矛盾是一些修饰的部分
	 * 思路：基于遍历算法(右中左)
	 * 要点：1、得知道当前节点层数，从而算出偏移大小(17*h))
	 * 			（父结点给的）
	 *      2、还需要知道当前结点是左节点(^^)还是右节点(vv)
	 *      	（父结点给的）
	 *      涉及到已知层推未知层，可以知道的是根节点的一切信息
	 *      通过根节点可以给其左右节点信息，左右节点可以继续给其子节点信息
	 */
	static int len = 17;//不管结点的val中的字符串长度是多少，统一设定未17，其它的用空格作为代替
	
	public static void printTree(Node head) {
		printInOrder(head,"H",0);
	}
	private static void printInOrder(Node head, String status, int h) {
		if(head == null) {
			return;
		}
		printInOrder(head.right,"v",h+1);
		String val = new String(String.valueOf(head.val));
		val = status + val + status;
		int lenM = val.length();
		int lenL = (len - lenM)/2;//表示前面需要空几个空格
		int lenR = len - lenL - lenM;
		val =getSpace(len*h) + getSpace(lenL) + val + getSpace(lenR);
		System.out.println(val);
		printInOrder(head.left,"^",h+1);
	}
	private static String getSpace(int num) {
		String space = " ";
		StringBuffer buf = new StringBuffer("");
		for(int i=0;i<num;i++) {
			buf.append(space);
		}
		return new String(buf);
	}

四、求前驱与后继（中序）

以找后继节点为例：
1、如果有右子树，那么后继节点是右子树上最左的节点（正向思考）
2、如果没有右子树，需要往上找，希望自己是上一个节点的左孩子，直至上一个节点已经为空（反向思考+正向验证）

public class FindLast {
	public class Node{
		int val;
		Node left;
		Node right;
		Node parent;
		
		public Node(int val) {
			this.val = val;
		}
	}
	/**
	 * 不是用递归进行实现
	 * @param node 所给节点
	 * @return 所给节点的后继节点
	 */
	public Node findLast(Node node) {
		if(node == null) {
			return null;
		}
		Node answer = null;
		Node right = node.right;
		if(right != null) {//如果右子树不为空
			while(right.left != null) {
				answer = right;
				right = right.left;
			}
		}
		if(right == null) {//如果右子树为空
			Node parent = node.parent;
			while(parent != null && parent.left != node) {
				answer = parent;
				parent = answer.parent;
			}
		}
		return answer;
	}
}

五、折纸（先序遍历“虚拟二叉树”）

从左往右打印折痕的凹凸性：如果是父节点的左孩子，那么是凹，如果是右孩子，那么是凸

	public static void printAllFolds(int N) {
		print(1,N,true);
	}
	/**
	 * @param i 当前节点所在的层数
	 * @param n 一共有多少层
	 * @param b true为凹 false为凸
	 * 往左是凹，往右是凸
	 */
	//中序遍历完全二叉树
	private static void print(int i, int N, boolean b) {
		if(i > N) {
			return;
		}
		print(i+1,N,true);
		String str = b ? "凹" : "凸";
		str += i;
		System.out.print(str);
		print(i+1,N,false);
	}