##1. 从上往下打印出二叉树的每个节点，同层节点从左至右打印。 思路： 这道题目其实就是“广度优先遍历二叉树”，所以我们可以通过以下步遍历二叉树：
1）将根节点压入队列； 2）获取根节点并出队，将根节点的数据加到List中； 3）将根节点的左、右节点顺序压入队列； 4）循环。。直到队列中无节点。
import java.util.*;
/**
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
*/
public class Solution {
public ArrayList<Integer> PrintFromTopToBottom(TreeNode root) {
ArrayList<Integer> array = new ArrayList<>(); //用来保存打印的列表
Queue<TreeNode> queue = new LinkedList<>(); //队列，用来装载二叉树的节点
if (root == null)
return array;
TreeNode node;
queue.offer(root); //首先将根节点入队
while (!queue.isEmpty()){
node = queue.poll(); //获取父节点并出队
array.add(node.val); //将父节点的数值保存到列表
if (node.left!=null) //如果父节点的左儿子不为空则将其入队
queue.offer(node.left);
if (node.right!=null) //如果父节点的右儿子不为空则将其入队
queue.offer(node.right);
}
return array;
}
}
###2. 重建二叉树 输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。 思路：
1、 首先要清楚前序、中序遍历的特点：前序遍历的数组的第一个元素一定是根节点，中序遍历的数组的某个元素的左边的子数组在二叉树中一定位于该元素对应节点的左边（即左子树），右边同原理。
2、 第一步：根据前序数组找到根节点，然后在中序数组中找到根节点对应的元素，则该元素在中序数组就是一个分界点，她的左边就是该节点的左子树所构成的，右边是她的右子树；
3、 第二步：但是如何获取她的左孩子节点呢（现在只得到左子树）？由前序遍历的特点我们知道，在前序数组中与该左子树对应的数组的第一个元素就是这个子树的根节点。由此循环。。
public class ReBuildTree {
/**
* 根据前序遍历数组、中序遍历数组重新构造二叉树
* 1. 通过前序数组可以知道根节点；
* 2. 通过中序数组可以知道根节点的左右子树
* 3. 所以具体的思路：通过前序得到根节点，然后在中序获得根节点左边的左子树、右边的右子树；然后再分别对左右子树循环直到只剩叶子。
* @param pre:前序遍历数组
* @param in：中序遍历数组
* @return
*/
public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
TreeNode root = reConstructBinaryTree(pre,0,pre.length-1,in,0,in.length-1);
return root;
}
public TreeNode reConstructBinaryTree(int [] pre,int preStart,int preEnd,int [] in,int inStart,int inEnd) {
if (preStart>preEnd || inStart>inEnd)
return null;
//前序数组的第一个元素一定是根节点（整棵树或子树）
TreeNode root = new TreeNode(pre[preStart]);
int pointcut = 0; //根节点在中序中的位置
//计算root节点在中序数组中的位置
for (int i=inStart;i<=inEnd;i++){
if (in[i] == pre[preStart]){
pointcut = i;
break;
}
}
//pointcut左边的数组则为root节点的左子树，右边的数组为右子树
//获取左孩子，左孩子在root节点在中序数组中左边的子数组中，但是中序数组无法直接找到一个子树的根节点，所以应该去这个子数组对应的前序中查找她
root.left = reConstructBinaryTree(pre,preStart+1,preStart+pointcut-inStart,in,inStart,pointcut-1);
root.right = reConstructBinaryTree(pre,preStart+pointcut-inStart+1,preEnd,in,pointcut+1,inEnd);
return root;
}
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
}