Minimum Depth of Binary Tree

Question

  1. Given a binary tree, find its minimum depth.
  3. The minimum depth is the number of nodes along the shortest path
  4. from the root node down to the nearest leaf node.
  6. Example
  7. Given a binary tree as follow:
  9.         1
  11.      /     \
  13.    2       3
  15.           /    \
  17.         4      5
  18. The minimum depth is 2

题解

注意审题，题中的最小深度指的是从根节点到最近的叶子节点（因为题中的最小深度是the number of nodes，故该叶子节点不能是空节点），所以需要单独处理叶子节点为空的情况。此题使用 DFS 递归实现比较简单。

Java

  1. /**
  2.  * Definition of TreeNode:
  3.  * public class TreeNode {
  4.  *     public int val;
  5.  *     public TreeNode left, right;
  6.  *     public TreeNode(int val) {
  7.  *         this.val = val;
  8.  *         this.left = this.right = null;
  9.  *     }
  10.  * }
  11.  */
  12. public class Solution {
  13.     /**
  14.      * @param root: The root of binary tree.
  15.      * @return: An integer.
  16.      */
  17.     public int minDepth(TreeNode root) {
  18.         if (root == null) return 0;
  20.         int leftDepth = minDepth(root.left);
  21.         int rightDepth = minDepth(root.right);
  23.         // current node is not leaf node
  24.         if (root.left == null) {
  25.             return 1 + rightDepth;
  26.         } else if (root.right == null) {
  27.             return 1 + leftDepth;
  28.         }
  30.         return 1 + Math.min(leftDepth, rightDepth);
  31.     }
  32. }

源码分析

建立好递归模型即可，左右子节点为空时需要单独处理下。

复杂度分析

每个节点遍历一次，时间复杂度 O(n). 不计栈空间的话空间复杂度 O(1).