java折纸问题（转化为二叉树问题）

java折纸问题（转化为二叉树问题）

一张纸条，由下向上对折，折痕凹，继续向上折，折痕分别是凹凹凸，以此类推
给定一个输入参数N，代表纸条从下向上对折N次，请从上向下打印折痕的方向
例如 n=1 凹 n=2 凹凹凸

这道题可以转化为二叉树的问题

第一次
凹

第二次
	凹
凹		凸

第三次
			凹
	凹				凸
凹		凸		凹		凸
…………………………

每次新增的线的凹凸性符合二叉树的规律，这道题可以转化为二叉树的问题来解决，每个父节点对应的都是凹，凸两个子节点，利用中序遍历来打印

private void printFoldPaper(int N){
	process(1, N, true);
}
//down判断是否是向下，向下方向则是凹，不是向下就是凸
private void process(int i, int N, boolean down){
	if (i > N){
		return;
	}
	process(i+1, N, true);
	System.out.print(down == true ? "凹" : "凸");
	process(i+1, N, false);
}

这道题很巧妙，可以转化成二叉树来解决，一般如果每次结果的变化都是2倍情况扩展的，可以考虑是否可以使用二叉树