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. }

C++

  1. /**
  2.  * Definition for a binary tree node.
  3.  * struct TreeNode {
  4.  *     int val;
  5.  *     TreeNode *left;
  6.  *     TreeNode *right;
  7.  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
  8.  * };
  9.  */
  10. class Solution {
  11. public:
  12.     int depth(TreeNode* n){
  13.         if(!n->left and !n->right) return 1;
  14.         if(!n->left) return 1 + depth(n->right);
  15.         if(!n->right) return 1 + depth(n->left);
  16.         return 1 + min(depth(n->left), depth(n->right));
  17.     }
  18.     int minDepth(TreeNode* root) {
  19.         if(!root) return 0;
  20.         return depth(root);
  21.     }
  22. };

源碼分析

建立好遞迴模型即可，左右子節點為空時需要單獨處理。

複雜度分析

每個節點遍歷一次，時間複雜度 O(n). 不計函數呼叫堆疊空間的話空間複雜度 O(1).