Java实现求二叉树的最大深度

标题：Java实现求二叉树的最大深度

public class TestMyTreeMaxLength12 { /** * 【递归】 * 执行结果： 通过 显示详情 执行用时：0 ms, 在所有 Java 提交中击败了100.00% 的用户 内存消耗：38.7 MB, 在所有 Java 提交中击败了81.41% 的用户 * @param p */ public int maxLen(IntNode p, int count) { if(p == null) { return count - 1; }else { int m1 = this.maxLen(p.left, count + 1); int m2 = this.maxLen(p.right, count + 1); return m1 > m2? m1 : m2; } } /** * 【递归的精髓 】 lc * 思想： if(p == 0) { return 0;} * else {return Math.max(左边最大深度 + 右边最大深度) + 1 } //双重递归 * * 执行结果： 通过 显示详情 执行用时：0 ms, 在所有 Java 提交中击败了100.00% 的用户 内存消耗：38 MB, 在所有 Java 提交中击败了99.71% 的用户 * @param p * @return */ public int maxLen03(IntNode p) { if(p == null) { return 0; }else { int m1 = this.maxLen03(p.left); int m2 = this.maxLen03(p.right); return Math.max(m1, m2) + 1; } } /** * 【非递归】 使用深度优先的后序遍历 * 执行用时：5 ms, 在所有 Java 提交中击败了5.27% 的用户 内存消耗：38.1 MB, 在所有 Java 提交中击败了99.05% 的用户 * @param p */ public int maxLen02(IntNode p) { Deque<IntNode> s = new LinkedList<>(); if(p == null) { return -1; } s.push(p); int count = 1; int max = 1; while(!s.isEmpty()) { while(s.peek().left != null) { //一直遍历左边 IntNode node = s.peek().left; s.push(node); count++; } IntNode node = s.peek().right; //取右节点 while(!s.isEmpty() && node == null) { max = count > max? count : max; System.out.print(s.peek().val + " "); IntNode m = s.pop(); count--; if(s.isEmpty()) { break; } node = s.peek().right; while(node == m) { //右支路 回退 m = s.pop(); count--; System.out.print(m.val + " "); if(s.isEmpty()) { break; } node = s.peek().right; } } if(!s.isEmpty() && node != null) { //若没有!s.isEmpty() f d g h e b i k j c a i k j c k j k s.push(node); count++; } } return max; } /** * 这个求最大深度的非递归，不用深度优先的后序遍历， * 而是用：非递归的广度遍历【轻巧】 * * 执行用时：36 ms, 在所有 Java 提交中击败了5.23% 的用户 内存消耗：38.1 MB, 在所有 Java 提交中击败了99.01% 的用户 * @param p * @return */ public int maxLen05(IntNode p) { System.out.println("使用广度遍历的非递归"); Queue<IntNode> q = new LinkedList<>(); if(p == null) { return 0; } q.offer(p); int count = 1; while(!q.isEmpty()) { int size = q.size(); for(int i = 0; i < size; i++) { IntNode node = q.poll(); System.out.print(node.val + " "); if(node.left != null) { q.offer(node.left); } if(node.right != null) { q.offer(node.right); } } if(!q.isEmpty()) { count++; } } return count; } @Test public void test02() { IntNode p1 = new IntNode('a'); IntNode p2 = new IntNode('b'); IntNode p3 = new IntNode('c'); IntNode p4 = new IntNode('d'); IntNode p5 = new IntNode('e'); IntNode p6 = new IntNode('f'); IntNode p7 = new IntNode('g'); IntNode p8 = new IntNode('h'); IntNode p9 = new IntNode('i'); IntNode p10 = new IntNode('j'); IntNode p11 = new IntNode('k'); p1.left = p2; p1.right = p3; p2.left = p4; // p2.right = p5; // p4.right = p6; p5.left = p7; p5.right = p8; p3.left = p9; p3.right = p10; // p10.right =p11; System.out.println("使用递归求最大深度"); int maxLen = this.maxLen(p1, 1); System.out.println("maxLen:" + maxLen); System.out.println(); System.out.println("使用递归求最大深度 【lc】"); maxLen = this.maxLen(p1, 1); System.out.println("maxLen:" + maxLen); System.out.println(); System.out.println("不使用递归的求最大深度"); maxLen = this.maxLen02(p1); System.out.println("maxLen:" + maxLen); System.out.println(); System.out.println("使用广度遍历的非递归"); maxLen = this.maxLen05(p1); System.out.println("maxLen:" + maxLen); System.out.println(); } }