第11节 二叉树的基本算法（下）

实现二叉树的按层遍历

• 其实就是宽度优先遍历，用队列
• 可以通过设置flag变量的方式，来发现某一层的结束

代码：

package class11;

import java.util.LinkedList;
import java.util.Queue;

/**
 * 	二叉树的按层遍历
 * 	其实是宽度优先遍历
 * @author yangyanchao
 *
 */
public class Test01_LevelTraversalBT {
	
	/**
	 * 	二叉树节点
	 * @author yangyanchao
	 *
	 */
	public static class TreeNode {
		public int value;
		public TreeNode left;
		public TreeNode right;
		public TreeNode(int value) {
			this.value = value;
		}
	}
	
	/**
	 * 	按层遍历 使用队列
	 * @param head
	 */
	public static void level(TreeNode head) {
		if(head == null) {
			return ;
		}
		System.out.print("Level order: ");
		Queue<TreeNode> queue = new LinkedList<TreeNode>();
		queue.add(head);
		TreeNode cur = null;
		while(!queue.isEmpty()) {
			cur = queue.poll();
			System.out.print(cur.value + " ");
			if(cur.left != null) {
				queue.add(cur.left);
			}
			if(cur.right != null) {
				queue.add(cur.right);
			}
		}
		System.out.println();
	}
	
	public static void main(String[] args) {
		TreeNode head = new TreeNode(1);
		head.left = new TreeNode(2);
		head.right = new TreeNode(3);
		head.left.left = new TreeNode(4);
		head.left.right = new TreeNode(5);
		head.right.left = new TreeNode(6);
		head.right.right = new TreeNode(7);

		level(head);
		System.out.println("========");
	}

}

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

• 先序方式序列化和反序列化
• 后序方式序列化和反序列化
• 按层方式序列化和反序列化

代码：

package class11;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

/**
 * 	使用先序、后序及按层遍历的方式序列化与反序列化二叉树结构
 * @author yangyanchao
 *
 */
public class Test02_SerializeAndReconstructTree {
	/**
	 * 	二叉树节点信息
	 * -二叉树可以通过先序、后序或者按层遍历的方式序列化和反序列化，
     * -以下代码全部实现了。
     * -但是，二叉树无法通过中序遍历的方式实现序列化和反序列化
     * -因为不同的两棵树，可能得到同样的中序序列，即便补了空位置也可能一样。
     * -比如如下两棵树
     *         __2
     *        /
     *       1
     * -和
     *       1__
     *          \
     *           2
     * -补足空位置的中序遍历结果都是{ null, 1, null, 2, null}
	 * @author yangyanchao
	 *
	 */
	public static class TreeNode {
		public int value;
		public TreeNode left;
		public TreeNode right;
		public TreeNode(int value) {
			this.value = value;
		}
	}
	
	/**
	 * 	先序-序列化
	 * @param head
	 * @return
	 */
	public static Queue<String> preSerialize(TreeNode head) {
		Queue<String> ans = new LinkedList<String>();
		preProcess(head, ans);
		return ans;
	}

	/**
	 * 	先序-序列化递归函数
	 * @param head
	 * @return
	 */
	private static void preProcess(TreeNode head, Queue<String> ans) {
		if(head == null) {
			ans.add(null);
		} else {
			ans.add(String.valueOf(head.value));
			preProcess(head.left, ans);
			preProcess(head.right, ans);
		}
	}
	
	/**
	 * 	先序-反序列化
	 * @param ans
	 * @return
	 */
	public static TreeNode buildByPreQueue(Queue<String> ans) {
		if(ans == null || ans.isEmpty()) {
			return null;
		}
		return buildByPreQueueProcess(ans);
	}
	
	/**
	 * 	先序-反序列化递归函数
	 * @param ans
	 * @return
	 */
	public static TreeNode buildByPreQueueProcess(Queue<String> ans) {
		String value = ans.poll();
		if(value == null) {
			return null;
		}
		TreeNode head = new TreeNode(Integer.parseInt(value));
		head.left = buildByPreQueueProcess(ans);
		head.right = buildByPreQueueProcess(ans);
		return head;
	}
	
	/**
	 * 	后序-序列化
	 * @param head
	 * @return
	 */
	public static Queue<String> posSerialize(TreeNode head) {
		if(head == null) {
			return null;
		}
		Queue<String> queue = new LinkedList<String>();
		posSerializeProcess(head, queue);
		return queue;
	}

	/**
	 * 	后序-序列化递归函数
	 * @param head
	 * @param queue
	 */
	private static void posSerializeProcess(TreeNode head, Queue<String> queue) {
		if(head == null) {
			queue.add(null);
		} else {
			posSerializeProcess(head.left, queue);
			posSerializeProcess(head.right, queue);
			queue.add(String.valueOf(head.value));
		}
	}
	
	/**
	 * 	后序-反序列化
	 * @param ans
	 * @return
	 */
	public static TreeNode buildByPosQueue(Queue<String> ans) {
		if(ans == null || ans.isEmpty()) {
			return null;
		}
		// 左右头 -> 头右左
		Stack<String> stack = new Stack<String>();
		while(!ans.isEmpty()) {
			stack.push(ans.poll());
		}
		return buildByPosQueueProcess(stack);
	}

	/**
	 * 	后序-反序列化递归函数
	 * @param stack
	 * @return
	 */
	private static TreeNode buildByPosQueueProcess(Stack<String> stack) {
		String value = stack.pop();
		if(value == null) {
			return null;
		}
		TreeNode head = new TreeNode(Integer.parseInt(value));
		// 先右
		head.right = buildByPosQueueProcess(stack);
		// 再左
		head.left = buildByPosQueueProcess(stack);
		return head;
	}
	
	
	/**
	 * 	按层遍历-序列化
	 * @param head
	 * @return
	 */
	public static Queue<String> levelSerialize(TreeNode head){
		Queue<String> ans = new LinkedList<String>();
		if(head == null) {
			ans.add(null);
		} else {
			ans.add(String.valueOf(head.value));
			Queue<TreeNode> nodeQueue = new LinkedList<TreeNode>();
			nodeQueue.add(head);
			while(!nodeQueue.isEmpty()) {
				head = nodeQueue.poll();
				if(head.left != null) {
					nodeQueue.add(head.left);
					ans.add(String.valueOf(head.left.value));
				} else {
					ans.add(null);
				}
				if(head.right != null) {
					nodeQueue.add(head.right);
					ans.add(String.valueOf(head.right.value));
				} else {
					ans.add(null);
				}
			}
		}
		return ans;
	}
	
	/**
	 * 	按层遍历-反序列化
	 * @param ans
	 * @return
	 */
	public static TreeNode buildByLevelQueue(Queue<String> ans) {
		if(ans == null || ans.isEmpty()) {
			return null;
		}
		TreeNode head = generateTreeNode(ans.poll());
		Queue<TreeNode> nodeQueue = new LinkedList<TreeNode>();
		if(head != null) {
			nodeQueue.add(head);
		}
		TreeNode cur = null;
		while(!ans.isEmpty()) {
			cur = nodeQueue.poll();
			cur.left =  generateTreeNode(ans.poll());
			cur.right =  generateTreeNode(ans.poll());
			if(cur.left != null) {
				nodeQueue.add(cur.left);
			}
			if(cur.right != null) {
				nodeQueue.add(cur.right);
			}
		}
		return head;
	}

	/**
	 * 	根据值生成节点信息
	 * @param value
	 * @return
	 */
	private static TreeNode generateTreeNode(String value) {
		if(value == null) {
			return null;
		}
		return new TreeNode(Integer.parseInt(value));
	}
	
	public static void main(String[] args) {
		int maxLevel = 5;
		int maxValue = 100;
		int testTimes = 1000000;
		System.out.println("test begin");
		for (int i = 0; i < testTimes; i++) {
			TreeNode head = generateRandomBST(maxLevel, maxValue);
			Queue<String> pre = preSerialize(head);
			Queue<String> pos = posSerialize(head);
			Queue<String> level = levelSerialize(head);
			TreeNode preBuild = buildByPreQueue(pre);
			TreeNode posBuild = buildByPosQueue(pos);
			TreeNode levelBuild = buildByLevelQueue(level);
			if (!isSameValueStructure(preBuild, posBuild) || !isSameValueStructure(posBuild, levelBuild)) {
				System.out.println("Oops!");
			}
		}
		System.out.println("test finish!");
		
	}
	

	// for test
	public static TreeNode generateRandomBST(int maxLevel, int maxValue) {
		return generate(1, maxLevel, maxValue);
	}

	// for test
	public static TreeNode generate(int level, int maxLevel, int maxValue) {
		if (level > maxLevel || Math.random() < 0.5) {
			return null;
		}
		TreeNode head = new TreeNode((int) (Math.random() * maxValue));
		head.left = generate(level + 1, maxLevel, maxValue);
		head.right = generate(level + 1, maxLevel, maxValue);
		return head;
	}

	// for test
	public static boolean isSameValueStructure(TreeNode head1, TreeNode head2) {
		if (head1 == null && head2 != null) {
			return false;
		}
		if (head1 != null && head2 == null) {
			return false;
		}
		if (head1 == null && head2 == null) {
			return true;
		}
		if (head1.value != head2.value) {
			return false;
		}
		return isSameValueStructure(head1.left, head2.left) && isSameValueStructure(head1.right, head2.right);
	}
	
}

实现多叉树与二叉树结构的互转

Leetcode (opens new window) 431题 Encode N-ary Tree to Binary Tree 属于Leetcode难题

题意：将多叉树结构转化为二叉树结构，并且能互转

转化逻辑：

多叉树的孩子节点 转化为二叉树节点的左节点(长兄)的右树上

代码：

package class11;

import java.util.ArrayList;
import java.util.List;

/**
 * 	实现多叉树与二叉树结构的互转
 * @author yangyanchao
 *
 */
public class Test03_EncodeNaryTreeToBinaryTree {
	/**
	 * 	多叉树节点
	 * @author yangyanchao
	 *
	 */
	public static class Node {
		public int value;
		public List<Node> children;
		public Node(int value) {
			this.value = value;
		}
		public Node(int value, List<Node> children) {
			this.value = value;
			this.children = children;
		}
	}
	
	/**
	 * 	二叉树节点
	 * @author yangyanchao
	 *
	 */
	public static class TreeNode {
		public int value;
		public TreeNode left;
		public TreeNode right;
		public TreeNode(int value) {
			this.value = value;
		}
	}
	/**
	 * 	多叉树编码二叉树
	 * 	二叉树解码多叉树
	 * @author yangyanchao
	 *
	 */
	class EncodeAndDecodeTree{
		/**
		 * 	多叉树编码二叉树
		 * @param head
		 * @return
		 */
		public TreeNode encode(Node root) {
			if(root == null) {
				return null;
			}
			TreeNode head = new TreeNode(root.value);
			head.left = encodeProcess(root.children);
			return head;
		}
		/**
		 * 	多叉树编码二叉树 递归函数
		 * @param children
		 * @return
		 */
		private TreeNode encodeProcess(List<Node> children) {
			TreeNode head = null;
			TreeNode cur = null;
			for(Node child : children) {
				TreeNode tNode = new TreeNode(child.value);
				if(head == null) {
					head = tNode;
				} else {
					// 这里的cur是指向这次循环上一个的节点
					cur.right = tNode;
				}
				cur = tNode;
				cur.left = encodeProcess(child.children);
			}
			return head;
		}
		/**
		 * 	二叉树解码多叉树
		 * @param head
		 * @return
		 */
		public Node decode(TreeNode root) {
			if(root == null) {
				return null;
			}
			return new Node(root.value, decodeProcess(root.left));
		}
		
		/**
		 * 	二叉树解码多叉树递归过程
		 * @param head
		 * @return
		 */
		private List<Node> decodeProcess(TreeNode root) {
			List<Node> children = new ArrayList<Node>();
			while(root != null) {
				children.add(new Node(root.value, decodeProcess(root.left)));
				root = root.right;
			}
			return children;
		}
	}
}

实现打印整颗二叉树的打印函数

代码：

package class11;

public class Code04_PrintBinaryTree {

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

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

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

	public static void main(String[] args) {
		Node head = new Node(1);
		head.left = new Node(-222222222);
		head.right = new Node(3);
		head.left.left = new Node(Integer.MIN_VALUE);
		head.right.left = new Node(55555555);
		head.right.right = new Node(66);
		head.left.left.right = new Node(777);
		printTree(head);

		head = new Node(1);
		head.left = new Node(2);
		head.right = new Node(3);
		head.left.left = new Node(4);
		head.right.left = new Node(5);
		head.right.right = new Node(6);
		head.left.left.right = new Node(7);
		printTree(head);

		head = new Node(1);
		head.left = new Node(1);
		head.right = new Node(1);
		head.left.left = new Node(1);
		head.right.left = new Node(1);
		head.right.right = new Node(1);
		head.left.left.right = new Node(1);
		printTree(head);

	}

}

求二叉树最宽的层有多少个节点

不使用Map的解题思路：额外空间O(1)

• 使用宽度优先遍历(按层遍历)，使用队列
• 定义层级最大节点数量maxCount、当前层级节点数量curCount、当前层级最后一个节点curEnd、下一个层级最后一个节点nextEnd、循环指向节点指针curNode
• 入队列则curCount++，弹出队列判断curEnd == curNode若是则curEnd=nextEnd maxCount与curCount求最大值赋值给maxCount curCount=0，若不是则有左孩子入队列nextEnd指向，有右孩子入队列nextEnd指向
• 周而复始

使用Map的解题思路：额外空间O(N)

• 使用宽度优先遍历(按层遍历)，使用队列
• 定义层级最大节点数量maxCount、当前层数curLevel、当前层的宽度curLevelNodes、哈希表记录每个节点的层数HashMap<TreeNode, Integer> map

代码：

package class11;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.Queue;

/**
 * 	求二叉树最宽的层有多少个节点
 * @author yangyanchao
 *
 */
public class Test05_TreeMaxWidth {
	
	/**
	 * 	二叉树节点
	 * @author yangyanchao
	 *
	 */
	public static class TreeNode {
		public int value;
		public TreeNode left;
		public TreeNode right;
		public TreeNode(int value) {
			this.value = value;
		}
	}
	
	/**
	 * 	求二叉树中最宽层的节点数量
	 * 	宽度优先遍历 按层遍历 记录每个层级上的节点数量
	 * 	额外空间O(1) 使用有限几个变量
	 * @param head
	 * @return
	 */
	public static int getTreeMaxWidthNoMap(TreeNode head) {
		if(head == null) {
			return 0;
		}
		Queue<TreeNode> queue = new LinkedList<TreeNode>();
		queue.add(head);
		TreeNode curEnd = head;
		TreeNode nextEnd = null;
		int maxCount = Integer.MIN_VALUE;
		int curCount = 0;
		TreeNode cur = null;
		while(!queue.isEmpty()) {
			cur = queue.poll();
			curCount++;
			if(cur.left != null) {
				queue.add(cur.left);
				nextEnd = cur.left;
			}
			if(cur.right != null) {
				queue.add(cur.right);
				nextEnd = cur.right;
			}
			if(cur == curEnd) {
				// 当前层的最后一个节点
				maxCount = Math.max(maxCount, curCount);
				curCount = 0;
				curEnd = nextEnd;
				nextEnd = null;
			}
		}
		return maxCount;
	}
	
	/**
	 * 	求二叉树中最宽层的节点数量
	 * 	宽度优先遍历 按层遍历 记录每个层级上的节点数量
	 * 	额外空间O(N) 使用Map记录每个节点所在层数
	 * @param head
	 * @return
	 */
	public static int getTreeMaxWidthUseMap(TreeNode head) {
		if(head == null) {
			return 0;
		}
		Queue<TreeNode> queue = new LinkedList<TreeNode>();
		HashMap<TreeNode, Integer> map = new HashMap<TreeNode, Integer>();
		map.put(head, 1);
		queue.add(head);
		int curLevel = 1; // 记录当前层
		int curLevelNodes = 0;// 记录当前层 目前是多少宽度了
		int maxCount = Integer.MIN_VALUE;
		TreeNode cur = null;
		// 宽度遍历
		while(!queue.isEmpty()) {
			cur = queue.poll();
			int curLevelNew = map.get(cur);
			if(cur.left != null) {
				queue.add(cur.left);
				map.put(cur.left, curLevelNew + 1);
			}
			if(cur.right != null) {
				queue.add(cur.right);
				map.put(cur.right, curLevelNew + 1);
			}
			if(curLevel == curLevelNew) {
				curLevelNodes++;
			} else {
				maxCount = Math.max(maxCount, curLevelNodes);
				curLevel++;
				curLevelNodes = 1;
			}
		}
		maxCount = Math.max(maxCount, curLevelNodes);
		return maxCount;
	}
	
	public static void main(String[] args) {
		int testTimes = 100000;
		int maxLevel = 10;
		int maxValue = 100;
		boolean succed = true;
		int res1 = -1;
		int res2 = -2;
		for(int i = 0; i < testTimes; i++) {
			TreeNode head = generateRandomBST(maxLevel, maxValue);
			res1 = getTreeMaxWidthUseMap(head);
			res2 = getTreeMaxWidthNoMap(head);
			if(res1 != res2) {
				succed = false;
				System.out.println(res1);
				System.out.println(res2);
				break;
				
			}
		}
		System.out.println(succed ? "Nice." : "ooVoo" );
	}

	/**
	 * 	生成随机二叉树
	 * @param maxLevel
	 * @param maxValue
	 * @return
	 */
	private static TreeNode generateRandomBST(int maxLevel, int maxValue) {
		return generateProcess(1, maxLevel, maxValue);
	}

	private static TreeNode generateProcess(int i, int maxLevel, int maxValue) {
		if(i > maxLevel || Math.random() < 0.5) {
			return null;
		}
		TreeNode head = new TreeNode((int)Math.random()*maxValue);
		head.left = generateProcess(i + 1, maxLevel, maxValue);
		head.right = generateProcess(i + 1, maxLevel, maxValue);
		return head;
	}
}

返回后继节点

后继节点：中序遍历(左头右)中的下一个节点

二叉树结构如下定义：

Class Node {
	V value;
	Node left;
	Node right;
	Node parent;
}

给你二叉树中的某个(X)节点，返回该节点的后继节点

不优化版本解题思路：

• 先找到头节点，中序遍历然后取X节点下一个节点，时间复杂度为O(N)

优化版本解题思路：

• 求解X节点的中序遍历中的下一个节点，既然是中序遍历则下一个节点一定不在X节点的左树上
• 由上分析则得出两种可能
• 一是X节点有右树，则查找右树的最左的节点
• 二是X节点无右树，则向上查找一直查找到节点是父节点的左孩子

代码：

package class11;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

/**
 * 	给你二叉树中的某个节点，返回该节点的后继节点
 * @author yangyanchao
 *
 */
public class Test06_SuccessorNode {
	/**
	 * 	二叉树节点
	 * @author yangyanchao
	 *
	 */
	public static class TreeNode {
		public int value;
		public TreeNode left;
		public TreeNode right;
		public TreeNode parent;
		public TreeNode(int value) {
			this.value = value;
		}
	}
	
	/**
	 * 	获取二叉树的X节点的后继节点
	 * 	中序遍历的下一个节点
	 * 	获取头节点 然后中序遍历找到下一个节点
	 * 	时间复杂度O(N)
	 * @param x
	 * @return
	 */
	public static TreeNode noOptimization(TreeNode x) {
		if(x == null) {
			return null;
		}
		TreeNode head = getHeadByX(x); // 获得头节点
		// 中序遍历 使用栈
		Stack<TreeNode> stack = new Stack<TreeNode>();
		Queue<TreeNode> ans = new LinkedList<TreeNode>();
		while(!stack.isEmpty() || head != null) {
			if(head != null) {
				stack.add(head);
				head = head.left;
			} else {
				head = stack.pop();
				ans.add(head);
				head = head.right;
			}
		}
		while(!ans.isEmpty()) {
			head = ans.poll();
			if(x == head) {
				break;
			}
		}
		return ans.poll();
	}
	
	/**
	 * 	获得头节点
	 * @param parent
	 * @return
	 */
	private static TreeNode getHeadByX(TreeNode node) {
		if(node == null) {
			return node;
		}
		while(node.parent != null) {
			node = node.parent;
		}
		return node;
	}

	/**
	 * 	获取二叉树的X节点的后继节点
	 * 	中序遍历的下一个节点
	 * 	时间复杂度O(K)
	 * 	K代表真实的距离数量
	 * @param x
	 * @return
	 */
	public static TreeNode getSuccessorNode(TreeNode x) {
		if(x == null) {
			return null;
		}
		if(x.right != null) {
			// x节点有右树 找该右树的最左的节点
			return getLeftMore(x.right);
		} else {
			// x节点无右树 向上找并判断是否是父节点的右孩子
			TreeNode node = x;
			TreeNode parent = node.parent;
			while(parent != null && parent.right == node) {
				node = parent;
				parent = node.parent;
			}
			return parent;
		}
	}

	private static TreeNode getLeftMore(TreeNode x) {
		if (x == null) {
			return x;
		}
		while(x.left != null) {
			x = x.left;
		}
		return x;
	}
	
	public static void main(String[] args) {
		TreeNode head = new TreeNode(6);
		head.parent = null;
		head.left = new TreeNode(3);
		head.left.parent = head;
		head.left.left = new TreeNode(1);
		head.left.left.parent = head.left;
		head.left.left.right = new TreeNode(2);
		head.left.left.right.parent = head.left.left;
		head.left.right = new TreeNode(4);
		head.left.right.parent = head.left;
		head.left.right.right = new TreeNode(5);
		head.left.right.right.parent = head.left.right;
		head.right = new TreeNode(9);
		head.right.parent = head;
		head.right.left = new TreeNode(8);
		head.right.left.parent = head.right;
		head.right.left.left = new TreeNode(7);
		head.right.left.left.parent = head.right.left;
		head.right.right = new TreeNode(10);
		head.right.right.parent = head.right;

		TreeNode test = head.left.left;
		System.out.println(test.value + " next: " + getSuccessorNode(test).value + " next1: " + noOptimization(test).value);
		test = head.left.left.right;
		System.out.println(test.value + " next: " + getSuccessorNode(test).value + " next1: " + noOptimization(test).value);
		test = head.left;
		System.out.println(test.value + " next: " + getSuccessorNode(test).value + " next1: " + noOptimization(test).value);
		test = head.left.right;
		System.out.println(test.value + " next: " + getSuccessorNode(test).value + " next1: " + noOptimization(test).value);
		test = head.left.right.right;
		System.out.println(test.value + " next: " + getSuccessorNode(test).value + " next1: " + noOptimization(test).value);
		test = head;
		System.out.println(test.value + " next: " + getSuccessorNode(test).value + " next1: " + noOptimization(test).value);
		test = head.right.left.left;
		System.out.println(test.value + " next: " + getSuccessorNode(test).value + " next1: " + noOptimization(test).value);
		test = head.right.left;
		System.out.println(test.value + " next: " + getSuccessorNode(test).value + " next1: " + noOptimization(test).value);
		test = head.right;
		System.out.println(test.value + " next: " + getSuccessorNode(test).value + " next1: " + noOptimization(test).value);
		test = head.right.right; // 10's next is null
		System.out.println(test.value + " next: " + getSuccessorNode(test) + " next1: " + noOptimization(test));
	}
}

折痕问题

题目：典型应用了二叉树的原理

请把一段纸条竖着放在桌子上，然后从纸条的下边向上方对折1次，压出折痕后展开。此时折痕是凹下去的，即折痕突起的方向指向纸条的背面。 如果从纸条的下边向上方连续对折2次，压出折痕后展开，此时有三条折痕，从上到下依次是下折痕、下折痕和上折痕。 给定一个输入参数N，代表纸条都从下边向上方连续对折N次。 请从上到下打印所有折痕的方向。 例如:N=1时，打印: 凹 N=2时，打印: 凹 凹 凸

代码：

package class11;

/**
 * 	折痕问题
 * @author yangyanchao
 *
 */
public class Test07_PagerFolding {
	
	/**
	 * -请把一段纸条竖着放在桌子上，然后从纸条的下边向上方对折1次，压出折痕后展开。此时折痕是凹下去的，即折痕突起的方向指向纸条的背面。 如果从纸条的下边向上方连续对折2次，压出折痕后展开，此时有三条折痕，从上到下依次是下折痕、下折痕和上折痕。 
	 * -给定一个输入参数N，代表纸条都从下边向上方连续对折N次。 请从上到下打印所有折痕的方向。 
	 * -例如:N=1时，打印: 凹 N=2时，打印: 凹 凹 凸 
	 */
	public static void printAllPageFolds(int N) {
		process(1, N, true);
		System.out.println();
	}
	
	/**
	 * 	中序遍历
	 * -当前你来了一个节点，脑海中想象的！
	 * -这个节点在第i层，一共有N层，N固定不变的
	 * -这个节点如果是凹的话，down = T
	 * -这个节点如果是凸的话，down = F
	 * -函数的功能：中序打印以你想象的节点为头的整棵树！
	 * @param i 当前层数
	 * @param n 一共多少层
	 * @param down true->凹 false->凸
	 */
	private static void process(int i, int n, boolean down) {
		if(i > n) {
			return;
		}
		process(i + 1, n, true);
		System.out.print(down ? "凹" : "凸");
		process(i + 1, n, false);
	}

	public static void main(String[] args) {
		printAllPageFolds(4);
	}
}