1.二叉树结构
class Node{ int value; Node left; node right; public Node(int data){ this.value = data; } }2.二叉树常考题型
易结合队列、栈，数组、链表等数据结构出题掌握图的基本遍历方式，深度优先与广度优先需要掌握递归函数的使用，自己设计递归过程与实际工作结合紧密3.遍历类型
先序遍历：中，左，右中序遍历：左，中，右后序遍历：左，右，根
结合下图讲解：
先序遍历：1245367 中序遍历：4251637 后序遍历：4526731
题目： 请用递归方式实现二叉树的先序、中序和后序的遍历打印。
给定一个二叉树的根结点root，请依次返回二叉树的先序，中序和后续遍历(二维数组的形式)。
代码：
import java.util.*; /* public class TreeNode { int val = 0; TreeNode left = null; TreeNode right = null; public TreeNode(int val) { this.val = val; } }*/ public class TreeToSequence { public int[][] convert(TreeNode root) { //边界条件判定 if(root==null){ return null; } List<Integer> preResult = new ArrayList<Integer>(); List<Integer> midResult = new ArrayList<Integer>(); List<Integer> lastResult = new ArrayList<Integer>(); preOrderTree(root,preResult); midOrderTree(root,midResult); lastOrderTree(root,lastResult); //结果数组 int[][] resultArr = new int[3][preResult.size()]; resultArr[0] = listToArray(preResult); resultArr[1] = listToArray(midResult); resultArr[2] = listToArray(lastResult); return resultArr; } //先序遍历 public void preOrderTree(TreeNode root,List<Integer> preResult){ if(root==null){ return; } preResult.add(root.val); preOrderTree(root.left,preResult); preOrderTree(root.right,preResult); } //中序遍历 public void midOrderTree(TreeNode root,List<Integer> midResult){ if(root==null){ return; } midOrderTree(root.left,midResult); midResult.add(root.val); midOrderTree(root.right,midResult); } //后遍历 public void lastOrderTree(TreeNode root,List<Integer> lastResult){ if(root==null){ return; } lastOrderTree(root.left,lastResult); lastOrderTree(root.right,lastResult); lastResult.add(root.val); } //list转化为数组 public int[] listToArray(List<Integer> list){ int[] temp = new int[list.size()]; for(int j=0;j<list.size();j++){ temp[j] = list.get(j); } return temp; } }题目： 请用非递归方式实现二叉树的先序、中序和后序的遍历打印。
给定一个二叉树的根结点root，请依次返回二叉树的先序，中序和后续遍历(二维数组的形式)。
代码：
import java.util.*; /* public class TreeNode { int val = 0; TreeNode left = null; TreeNode right = null; public TreeNode(int val) { this.val = val; } }*/ public class TreeToSequence { public int[][] convert(TreeNode root) { //边界条件判断 if(root==null){ return null; } List<Integer> preList = new ArrayList<Integer>(); List<Integer> midList = new ArrayList<Integer>(); List<Integer> lastList = new ArrayList<Integer>(); preOrderTree(root,preList); midOrderTree(root,midList); lastOrderTree(root,lastList); int[][] result = new int[3][]; result[0] = listToArray(preList); result[1] = listToArray(midList); result[2] = listToArray(lastList); return result; } //先序遍历 public void preOrderTree(TreeNode root,List<Integer> list){ if(root==null){ return; } //申请一个新的栈结构 Stack<TreeNode> stack = new Stack<TreeNode>(); stack.push(root); //定义一个临时存储节点 TreeNode temp = null; while(!stack.empty()){ temp = stack.pop(); list.add(temp.val); if(temp.right!=null){ stack.push(temp.right); } if(temp.left!=null){ stack.push(temp.left); } } } //中序遍历 public void midOrderTree(TreeNode root,List<Integer> list){ if(root==null){ return; } Stack<TreeNode> stack = new Stack<TreeNode>(); TreeNode cur = root; while(!stack.empty()||cur!=null){ if(cur!=null){ stack.push(cur); cur = cur.left; }else{ cur = stack.pop(); list.add(cur.val); cur = cur.right; } } } //后序遍历 public void lastOrderTree(TreeNode root,List<Integer> list){ if(root==null){ return; } Stack<TreeNode> stack1 = new Stack<TreeNode>(); Stack<TreeNode> stack2 = new Stack<TreeNode>(); stack1.push(root); while(!stack1.empty()){ TreeNode temp = stack1.pop(); stack2.push(temp); if(temp.left!=null){ stack1.push(temp.left); } if(temp.right!=null){ stack1.push(temp.right); } } while(!stack2.empty()){ list.add(stack2.pop().val); } } //list转化为数组 public int[] listToArray(List<Integer> list){ int[] temp = new int[list.size()]; for(int j=0;j<list.size();j++){ temp[j] = list.get(j); } return temp; } }题目： 有一棵二叉树，请设计一个算法，按照层次打印这棵二叉树。
给定二叉树的根结点root，请返回打印结果，结果按照每一层一个数组进行储存，所有数组的顺序按照层数从上往下，且每一层的数组内元素按照从左往右排列。保证结点数小于等于500。
代码：
import java.util.*; /* public class TreeNode { int val = 0; TreeNode left = null; TreeNode right = null; public TreeNode(int val) { this.val = val; } }*/ public class TreePrinter { public int[][] printTree(TreeNode root) { //边界条件判断 if(root==null){ return null; } //存储分层打印结果 ArrayList<ArrayList<TreeNode>> resultList = new ArrayList<ArrayList<TreeNode>>(); //用于判断换行的两个变量 //last表示每行的最后一个元素 //nLast表示当前遍历到的节点 TreeNode last = root; TreeNode nLast = root; //模拟队列，宽度优先 LinkedList<TreeNode> queue = new LinkedList<TreeNode>(); queue.addFirst(root); //存储每一行的元素的临时结构 ArrayList<TreeNode> tempList = new ArrayList<TreeNode>(); while(queue.size()!=0){ //每次弹出头部元素 TreeNode temp = queue.pollFirst(); tempList.add(temp); //左孩子不空，加入队列 if(temp.left!=null){ queue.addLast(temp.left); nLast = temp.left; } //右孩子不空，加入队列 if(temp.right!=null){ queue.addLast(temp.right); nLast = temp.right; } //若last=temp,说明遍历到了行尾元素，换行，并将last下移到下一行的末尾 if(last==temp){ last = nLast; resultList.add(tempList); tempList = new ArrayList<TreeNode>(); } } //list转化为数组 int[][] result = new int[resultList.size()][]; for(int i=0;i<resultList.size();i++){ result[i] = new int[resultList.get(i).size()]; for(int j=0;j<resultList.get(i).size();j++){ result[i][j] = resultList.get(i).get(j).val; } } return result; } }题目： 首先我们介绍二叉树先序序列化的方式，假设序列化的结果字符串为str，初始时str等于空字符串。先序遍历二叉树，如果遇到空节点，就在str的末尾加上“#!”，“#”表示这个节点为空，节点值不存在，当然你也可以用其他的特殊字符，“!”表示一个值的结束。如果遇到不为空的节点，假设节点值为3，就在str的末尾加上“3!”。现在请你实现树的先序序列化。
给定树的根结点root，请返回二叉树序列化后的字符串。
代码：
import java.util.*; /* public class TreeNode { int val = 0; TreeNode left = null; TreeNode right = null; public TreeNode(int val) { this.val = val; } }*/ public class TreeToString { public String toString(TreeNode root) { //边界条件判定 if(root==null){ return "#!"; } StringBuffer sb = new StringBuffer(); preOrder(root,sb); return sb.toString(); } public void preOrder(TreeNode root,StringBuffer sb){ if(root==null){ sb.append("#!"); }else{ sb.append(root.val+"!"); preOrder(root.left,sb); preOrder(root.right,sb); } } }题目： 请把纸条竖着放在桌⼦上，然后从纸条的下边向上⽅对折，压出折痕后再展 开。此时有1条折痕，突起的⽅向指向纸条的背⾯，这条折痕叫做“下”折痕 ；突起的⽅向指向纸条正⾯的折痕叫做“上”折痕。如果每次都从下边向上⽅ 对折，对折N次。请从上到下计算出所有折痕的⽅向。
给定折的次数n,请返回从上到下的折痕的数组，若为下折痕则对应元素为”down”,若为上折痕则为”up”.
测试样例： 1 返回：[“down”]
代码：
import java.util.*; public class FoldPaper { public String[] foldPaper(int n) { //边界条件判定 if(n<=0){ return null; } ArrayList<String> result = new ArrayList<String>(); fold(1,n,true,result); String[] str = new String[result.size()]; for(int i = 0; i < result.size(); i++){ str[i] = result.get(i); } return str; } public void fold(int i,int n,boolean down,ArrayList<String> list){ //判断边界，是否大于给定次数n if(i>n){ return; } //，折纸的折痕顺序为中序遍历结果，左边的孩子全为下折痕，右边的孩子全为上折痕 fold(i+1,n,true,list); list.add(down == true?"down":"up"); fold(i+1,n,false,list); } }