考察点：二叉树
实现二叉树的深度方式有两种，递归以及非递归。
①递归实现：
为了求树的深度，可以先求其左子树的深度和右子树的深度，可以用递归实现，递归的出口就是节点为空。返回值为0；
②非递归实现：
利用层次遍历的算法，设置变量level记录当前节点所在的层数，设置变量last指向当前层的最后一个节点，当处理完当前层的最后一个节点，让level指向+1操作。设置变量cur记录当前层已经访问的节点的个数，当cur等于last时，表示该层访问结束。
层次遍历在求树的宽度、输出某一层节点，某一层节点个数，每一层节点个数都可以采取类似的算法。
树的宽度：在树的深度算法基础上，加一个记录访问过的层节点个数最多的变量max,在访问每层前max与last比较，如果max比较大，max不变，如果max小于last，把last赋值给max;
代码解释：
import java.util.ArrayList;import java.util.Scanner;public class Main{ // 定义节点 class Node{ int val; Nodeleft; Node right; public Node(int val) { this.val = val; } } public ArrayList<Integer> gzy; // 保存根左右的序列 public ArrayList<Integer> zgy; // 保存左跟右的序列 public ArrayList<Node> pack; // 保存已经排好的节点 public static void main(String[] args) { Main main = new Main(); main.getResult(); } public void getResult() { //init Scannerscanner = new Scanner(System.in); int count = scanner.nextInt(); gzy = new ArrayList<>(); zgy = new ArrayList<>(); for(int i = 0; i < count; i++) { gzy.add(scanner.nextInt()); } for(int j = 0; j < count; j++) { zgy.add(scanner.nextInt()); } pack= new ArrayList<>(); // 已经还原的节点 //exception if(count== 1) { System.out.println(gzy.get(0)); return; } // 构造最左侧节点的二叉树 Node node = new Node(gzy.get(0)); pack.add(node); int index1 = 1; // 根左右的下标 Node tmp = node; while(gzy.get(index1) != zgy.get(0)) { // 如果没访问到最左边的叶子节点,继续还原最左侧二叉树 tmp.left = new Node(gzy.get(index1++)); tmp = tmp.left; pack.add(tmp); } tmp.left = new Node(gzy.get(index1++)); pack.add(tmp.left); // 加入剩余的节点完善二叉树 for(int k = index1; k < gzy.size(); k++) { fillErCS(gzy.get(k)); } // 层次遍历 ArrayList<Node> res = new ArrayList<>(); res.add(node); int num = 0; while(res.size()!= num) { System.out.print(res.get(num).val + ""); if(res.get(num).left != null) { res.add(res.get(num).left); } if(res.get(num).right != null) { res.add(res.get(num).right); } num++; } } // 将值为val的节点加入二叉树 private void fillErCS(int val) { int index = zgy.indexOf(val); // 每一个遍历的节点都是val节点的根或者在其左边 for(int i = index-1; i >= 0; i--) { if(findNode(zgy.get(i)) != null) { // 找到待插入节点的根节点或者其左边的节点 Node node = findNode(zgy.get(i)); insert(node,val); break; } } } // 将节点val插入二叉树 private void insert(Node node, int val) { if(zgy.indexOf(node.val)> zgy.indexOf(val)) { // node在待插入节点的右边 if(node.left == null) { node.left= new Node(val); pack.add(node.left); return; } insert(node.left, val); } else{ //node在待插入节点的左边或是其根 if(node.right == null) { node.right= new Node(val); pack.add(node.right); return; } insert(node.right, val); } } // 根据val找到pack里的节点 private Node findNode(int val) { for(Node node : pack) { if(node.val == val) { return node; } } return null; }}
