题解 | #二叉树的最小深度# [P3]

这题因为是找最浅的leaf node，明显BFS会更合适。
那对于二叉树，BFS就是levelOrder traversal。找到第一个leaf就直接return当前深度。
时间O(n) 空间O(n)

import java.util.*;

public class Solution {
    public int run (TreeNode root) {
      if (root == null) return 0;
      
      Queue<TreeNode> q = new LinkedList<>();
      q.offer(root);
      int depth = 0;
      while (!q.isEmpty()) {
        depth++;
        int levelSize = q.size();
        for (int i = 0; i < levelSize; i++) {
          TreeNode head = q.poll();
          // 遇到第一个leaf node就直接返回当前depth.
          if (head.left == null && head.right == null) return depth;
          if (head.left != null) q.offer(head.left);
          if (head.right != null) q.offer(head.right);
        }
      }
      
      // should not get here
      return 0;
    }
}