LeetCode | Minimum Depth of Binary Tree

题目

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.

题目很简单，需要尽可能写得精炼。

有递归（DFS，解法1）和非递归（BFS，解法2）两种写法。

解法1

public class MinimumDepthOfBinaryTree {
	public int minDepth(TreeNode root) {
		if (root == null) {
			return 0;
		}
		int left = minDepth(root.left);
		int right = minDepth(root.right);
		if (left == 0) {
			return right + 1;
		}
		if (right == 0) {
			return left + 1;
		}
		return Math.min(left, right) + 1;
	}
}

import java.util.LinkedList;
import java.util.Queue;

public class MinimumDepthOfBinaryTree {
	public int minDepth(TreeNode root) {
		if (root == null) {
			return 0;
		}

		// bfs
		Queue
  
    currentLevel = new LinkedList
   
    (); Queue
    
      nextLevel = new LinkedList
     
      (); int level = 1; currentLevel.add(root); while (true) { TreeNode node = currentLevel.poll(); if (node.left == null && node.right == null) { return level; } if (node.left != null) { nextLevel.add(node.left); } if (node.right != null) { nextLevel.add(node.right); } if (currentLevel.isEmpty()) { // swap Queue
      
        temp = currentLevel; currentLevel = nextLevel; nextLevel = temp; ++level; } } } }