二叉树的最大深度
给定一个二叉树 root ，返回其最大深度。
二叉树的 最大深度是指从根节点到最远叶子节点的最长路径上的节点数。
示例 1：
输入：root = [3,9,20,null,null,15,7] 输出：3
示例 2：
输入：root = [1,null,2] 输出：2
【思路】
方法一：递归的方式
递归的出口：root==null
递归的条件：树的最大高度=1+maxDepth(左子树，右子树)
public int maxDepth(TreeNode root) { if (root == null) { return 0; } else { int left = maxDepth(root.left); int right = maxDepth(root.right); return Math.max(left, right) + 1; } }
方法二：层次遍历
使用迭代法的话，使用层序遍历是最为合适的，因为最大的深度就是二叉树的层数，和层序遍历的方式极其吻合。在二叉树中，一层一层的来遍历二叉树，记录一下遍历的层数就是二叉树的深度。
public int maxDepth(TreeNode root) { int depth = 0; if (root == null) return depth; Queue<TreeNode> queue = new LinkedList<>(); queue.add(root); // 辅助队列不为空 while (!queue.isEmpty()) { int levelSize = queue.size(); depth++; for (int i = 0; i < levelSize; i++) { TreeNode temp = queue.poll(); if (temp.left != null) { queue.add(temp.left); } if (temp.right != null) { queue.add(temp.right); } } } return depth; }
