Minimum Depth of Binary Tree 解答

Question

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.

Solution 1 -- Recursion

Problems related with tree can always be solved by recursion. We need only consider three situations:

1. parent node

2. left child node

3. right chile node

Time complexity O(n), space cost O(1).

 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 public class Solution {
11     public int minDepth(TreeNode root) {
12         if (root == null)
13             return 0;
14         if (root.left == null)
15             return minDepth(root.right) + 1;
16         if (root.right == null)
17             return minDepth(root.left) + 1;
18         return Math.min(minDepth(root.left), minDepth(root.right)) + 1;
19     }
20 }

Solution 2 -- Iteration

We can also solve this problem by visiting the tree level by level. Time complexity O(n), space cost O(n).

Notice that using ArrayList will save almost half time compared with using ArrayDeque. Actually, we need not to pop staff here.

 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 public class Solution {
11     public int minDepth(TreeNode root) {
12         if (root == null)
13             return 0;
14         List<TreeNode> current = new ArrayList<TreeNode>();
15         List<TreeNode> next;
16         current.add(root);
17         int result = 1;
18         while (current.size() > 0) {
19             next = new ArrayList<TreeNode>();
20             int length = current.size();
21             for (TreeNode tmpNode : current) {
22                 // If tmpNode is leaf node
23                 if (tmpNode.left == null && tmpNode.right == null)
24                     return result;
25                 if (tmpNode.left != null)
26                     next.add(tmpNode.left);
27                 if (tmpNode.right != null)
28                     next.add(tmpNode.right);
29             }
30             current = next;
31             result++;
32         }
33         return result;
34     }
35 }

Discussion

Recursion is not always the time consuming solution. For example, in this problem, every node has been calculated height for only once, so there's no redundance. However, for Fibonacci problem, when we calculate F(5), we get F(5) = F(4) + F(3), which is redundant calculation. Under this circumtance, we should use Dynamic Programming.