Given a binary tree, find its minimum depth.

    The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.

    Note: A leaf is a node with no children.

    Example:

    Given binary tree [3,9,20,null,null,15,7],

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

    return its minimum depth = 2.

    题意

    找到给定树从根到叶结点(两子树都为空的结点)的最短距离。

    思路

    递归或迭代。

    代码实现 - 递归

    1. /**
    2.  * Definition for a binary tree node.
    3.  * public class TreeNode {
    4.  *     int val;
    5.  *     TreeNode left;
    6.  *     TreeNode right;
    7.  *     TreeNode(int x) { val = x; }
    8.  * }
    9.  */
    10. class Solution {
    11.     public int minDepth(TreeNode root) {
    12.         if (root == null) {
    13.             return 0;
    14.         }
    16.         int lDepth = minDepth(root.left);
    17.         int rDepth = minDepth(root.right);
    19.         if (lDepth == 0) {
    20.             return rDepth + 1;
    21.         } else if (rDepth == 0) {
    22.             return lDepth + 1;
    23.         } else {
    24.             return Math.min(lDepth, rDepth) + 1;
    25.         }
    26.     }
    27. }

    代码实现 - 迭代

    1. /**
    2.  * Definition for a binary tree node.
    3.  * public class TreeNode {
    4.  *     int val;
    5.  *     TreeNode left;
    6.  *     TreeNode right;
    7.  *     TreeNode(int x) { val = x; }
    8.  * }
    9.  */
    10. class Solution {
    11.     public int minDepth(TreeNode root) {
    12.         if (root == null) {
    13.             return 0;
    14.         }
    16.         Queue<TreeNode> q = new ArrayDeque<>();
    17.         int depth = 0;
    18.         q.offer(root);
    19.         while (!q.isEmpty()) {
    20.             depth++;
    21.             int size = q.size();
    22.             for (int i = 0; i < size; i++) {
    23.                 TreeNode cur = q.poll();
    24.                 // 第一次找到叶结点，说明已经为最短距离
    25.                 if (cur.left == null && cur.right == null) {
    26.                     return depth;
    27.                 }
    28.                 if (cur.left != null) {
    29.                     q.offer(cur.left);
    30.                 }
    31.                 if (cur.right != null) {
    32.                     q.offer(cur.right);
    33.                 }
    34.             }
    36.         }
    37.         return depth;
    38.     }
    39. }