给定一个二叉树，找出其最大深度。
二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
说明：叶子节点是指没有子节点的节点。

示例：
给定二叉树 [3,9,20,null,null,15,7]

  1.     3
  2.    / \
  3.   9  20
  4.     /  \
  5.    15   7

返回它的最大深度 3。

分析

对于根节点来说，如果左子树的深度大于右子树的深度，则整棵树的深度是左子树深度 + 1(根节点)，反之整棵树的深度是右子树深度 + 1(根节点)。
那么每次递归要做的事情就是分别计算左子树的深度和右子树的深度，并且做比较取最大值，最后树的深度就是最大值 + 1

完整递归算法

  1. public int maxDepth(TreeNode root) {
  2.     if(root == null) {
  3.         return 0;
  4.     } else {
  5.         int leftDepth = maxDepth(root.left);
  6.         int rightDepth = maxDepth(root.right);
  7.         return Math.max(leftDepth, rightDepth) + 1;
  8.     }
  9. }

递归转迭代

递归转迭代可以按照下方模式处理：

  1. private int maxDepth(TreeNode root) {
  2.     Queue<TreeNode> queue = new LinkedList<TreeNode>();
  3.     queue.offer(root);
  4.     int depth = 0;
  5.     while(!queue.isEmpty()) {
  6.         // TODO 每次循环需要做的事情
  7.         depth++;
  8.     }
  9.     return depth;
  10. }

现在关键是分析出每次循环需要做的事情！
拿示例中的二叉树来分析

  1.     3
  2.    / \
  3.   9  20
  4.     /  \
  5.    15   7
  7. 队列：3
  9. 取出队列中的头元素 3 
  10. 放入 9，20

完整迭代算法

  1. public int maxDepth(TreeNode root) {
  2.     if (root == null) {
  3.         return 0;
  4.     }
  5.     Queue<TreeNode> queue = new LinkedList<TreeNode>();
  6.     queue.offer(root);
  7.     int ans = 0;
  8.     while (!queue.isEmpty()) {
  9.         int size = queue.size();
  10.         while (size > 0) {
  11.             TreeNode node = queue.poll();
  12.             if (node.left != null) {
  13.                 queue.offer(node.left);
  14.             }
  15.             if (node.right != null) {
  16.                 queue.offer(node.right);
  17.             }
  18.             size--;
  19.         }
  20.         ans++;
  21.     }
  22.     return ans;
  23. }