七、二叉树的最大深度问题
需求：
给定一棵树，请计算树的最大深度(树的根节点到最远叶子结点的最长路径上的结点数)
上面这棵树的最大深度为4。
实现：
我们在1.4中创建的树上，添加如下的API求最大深度：
public int maxDepth() ：计算整个树的最大深度
private int maxDepth(Node x): 计算指定树x的最大深度
实现步骤
1.如果根结点为空，则最大深度为0；
2.计算左子树的最大深度；
3.计算右子树的最大深度；
4.当前树的最大深度=左子树的最大深度和右子树的最大深度中的较大者+1
代码：
// 计算整个树的最大深度 public int maxDepth() { return maxDepth(root); } //计算指定树x的最大深度 private int maxDepth(Node x) { //1.如果根结点为空，则最大深度为0； if (x == null) { return 0; } int max = 0; int maxL = 0; int maxR = 0; //2.计算左子树的最大深度； if (x.left != null) { maxL = maxDepth(x.left); } //3.计算右子树的最大深度； if (x.right != null) { maxR = maxDepth(x.right); } //4.当前树的最大深度=左子树的最大深度和右子树的最大深度中的较大者+1 max = maxL > maxR ? maxL + 1 : maxR + 1; return max; } //测试代码 public class Test { public static void main(String[] args) throws Exception { BinaryTree<String, String> bt = new BinaryTree<>(); bt.put("E", "5"); bt.put("B", "2"); bt.put("G", "7"); bt.put("A", "1"); bt.put("D", "4"); bt.put("F", "6"); bt.put("H", "8"); bt.put("C", "3"); int i = bt.maxDepth(); System.out.println(i); } }
八、折纸问题
需求：
请把一段纸条竖着放在桌子上，然后从纸条的下边向上方对折1次，压出折痕后展开。此时 折痕是凹下去的，即折痕突起的方向指向纸条的背面。如果从纸条的下边向上方连续对折2 次，压出折痕后展开，此时有三条折痕，从上到下依次是下折痕、下折痕和上折痕。
给定一 个输入参数N，代表纸条都从下边向上方连续对折N次，请从上到下打印所有折痕的方向 例如：N=1时，打印： down；N=2时，打印： down down up
分析：
我们把对折后的纸张翻过来，让粉色朝下，这时把第一次对折产生的折痕看做是根结点，那第二次对折产生的下折痕就是该结点的左子结点，而第二次对折产生的上折痕就是该结点的右子结点，这样我们就可以使用树型数据结构来描述对折后产生的折痕。
这棵树有这样的特点：
1.根结点为下折痕；
2.每一个结点的左子结点为下折痕；
3.每一个结点的右子结点为上折痕；
实现步骤：
1.定义结点类
2.构建深度为N的折痕树；
3.使用中序遍历，打印出树中所有结点的内容；
构建深度为N的折痕树：
1.第一次对折，只有一条折痕，创建根结点；
2.如果不是第一次对折，则使用队列保存根结点；
3.循环遍历队列：
3.1从队列中拿出一个结点；
3.2如果这个结点的左子结点不为空，则把这个左子结点添加到队列中；
3.3如果这个结点的右子结点不为空，则把这个右子结点添加到队列中；
3.4判断当前结点的左子结点和右子结点都不为空，如果是，则需要为当前结点创建一个值为down的左子结点，一个值为up的右子结点。
代码：
public class PaperFolding { public static void main(String[] args) { //构建折痕树 Node tree = createTree(3); //遍历折痕树，并打印 printTree(tree); } //3.使用中序遍历，打印出树中所有结点的内容； private static void printTree(Node tree) { if (tree==null){ return; } printTree(tree.left); System.out.print(tree.item+","); printTree(tree.right); } //2.构建深度为N的折痕树； private static Node createTree(int N) { Node root = null; for (int i = 0; i <N ; i++) { if (i==0){ //1.第一次对折，只有一条折痕，创建根结点； root = new Node("down",null,null); }else{ //2.如果不是第一次对折，则使用队列保存根结点； Queue<Node> queue = new Queue<>(); queue.enqueue(root); //3.循环遍历队列： while(!queue.isEmpty()){ //3.1从队列中拿出一个结点； Node tmp = queue.dequeue(); //3.2如果这个结点的左子结点不为空，则把这个左子结点添加到队列中； if (tmp.left!=null){ queue.enqueue(tmp.left); } //3.3如果这个结点的右子结点不为空，则把这个右子结点添加到队列中； if (tmp.right!=null){ queue.enqueue(tmp.right); } //3.4判断当前结点的左子结点和右子结点都不为空，如果是，则需要为当前结点创建一个值为down的左子结点，一个值为up的右子结点。 if (tmp.left==null && tmp.right==null){ tmp.left = new Node("down",null,null); tmp.right = new Node("up",null,null); } } } } return root; } //1.定义结点类 private static class Node{ //存储结点元素 String item; //左子结点 Node left; //右子结点 Node right; public Node(String item, Node left, Node right) { this.item = item; this.left = left; this.right = right; } } }
