P22 二叉树的最大深度

描述#

这个题目说的是，给你一棵二叉树，你要找到从根节点到最远叶子节点的深度。

比如说，给你的二叉树是
1

/   

2     4
/ 

8  16
这棵树有 3 个叶子节点，分别是 2，8，16。最远的叶子节点是 8 和 16，根节点到 8 或 16 都有 3 个节点，因此最大深度是 3。

代码#

public class AlgoCasts {

  public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
      val = x;
    }
  }

  // Time: O(n), Space: (n)
  public int maxDepth(TreeNode root) {
    if (root == null) return 0;
    return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
  }

  // Time: O(n), Space: O(n)
  public int maxDepthIterative(TreeNode root) {
    if (root == null) return 0;
    Queue<TreeNode> q = new LinkedList<>();
    q.add(root);
    int depth = 0;

    while (!q.isEmpty()) {
      int size = q.size();
      for (int i = 0; i < size; ++i) {
        TreeNode s = q.poll();
        if (s.left != null) q.add(s.left);
        if (s.right != null) q.add(s.right);
      }
      ++depth;
    }

    return depth;
  }

}