LeetCode - Easy - 111. Minimum Depth of Binary Tree

小鱼儿 2022-12-28 09:20 100阅读 0赞

## Topic ##

*  Tree
 *  Breadth-first Search
 *  Depth-first Search

## Description ##

[https://leetcode.com/problems/minimum-depth-of-binary-tree/][https_leetcode.com_problems_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.

**Note**: A leaf is a node with no children.

**Example 1**:

3
       / \
      9  20
         / \
       15   7
    
    Input: root = [3,9,20,null,null,15,7]
    Output: 2

**Example 2**:

2
     \
      3
       \
        4
         \
          5
           \
            6
    
    Input: root = [2,null,3,null,4,null,5,null,6]
    Output: 5

**Constraints**:

*  The number of nodes in the tree is in the range \[0, 10⁵\].
 *  \-1000 <= Node.val <= 1000

## Analysis ##

方法一：DFS

方法二：BFS

## Submission ##

import java.util.LinkedList;
    import java.util.Queue;
    
    import com.lun.util.BinaryTree.TreeNode;
    
    public class MinimumDepthOfBinaryTree { 
    	
    	//方法一：DFS
    	public int minDepth1(TreeNode root) { 
    		if (root == null)
    			return 0;
    		int left = minDepth1(root.left), right = minDepth1(root.right);
    		return (left == 0 || right == 0) ? Math.max(left, right) + 1 : Math.min(left, right) + 1;//不是简单的返回Math.min(left, right) + 1，当左右子树其中一个高度为0，则选其中最大高度者（也就是另一子树高度）+ 1。这有点反直觉。
    	}
    
    	//方法二：BFS
    	public int minDepth2(TreeNode root) { 
    		if (root == null) return 0;
    		int depth = 1;
    		Queue<TreeNode> q = new LinkedList<TreeNode>();
    		q.offer(root);
    		while (!q.isEmpty()) { 
    			int size = q.size();
    			// for each level
    			for (int i = 0; i < size; i++) { 
    				TreeNode node = q.poll();
    				if (node.left == null && node.right == null) { 
    					return depth;
    				}
    				if (node.left != null) { 
    					q.offer(node.left);
    				}
    				if (node.right != null) { 
    					q.offer(node.right);
    				}
    			}
    			depth++;
    		}
    		return depth;
    	}
    }

## Test ##

import static org.junit.Assert.*;
    import org.junit.Test;
    
    import com.lun.util.BinaryTree.TreeNode;
    
    public class MinimumDepthOfBinaryTreeTest { 
    
    	@Test
    	public void test1() { 
    		MinimumDepthOfBinaryTree obj = new MinimumDepthOfBinaryTree();
    
    		TreeNode root = new TreeNode(3);
    		
    		root.left = new TreeNode(9);
    		root.right = new TreeNode(20);
    		
    		root.right.left = new TreeNode(15);
    		root.right.right = new TreeNode(7);
    		
    		assertEquals(2, obj.minDepth1(root));
    		assertEquals(2, obj.minDepth2(root));
    	}
    	
    	@Test
    	public void test2() { 
    		MinimumDepthOfBinaryTree obj = new MinimumDepthOfBinaryTree();
    		
    		TreeNode root = new TreeNode(2);
    		root.right = new TreeNode(3);
    		root.right.right = new TreeNode(4);
    		root.right.right.right = new TreeNode(5);
    		root.right.right.right.right = new TreeNode(6);
    
    		assertEquals(5, obj.minDepth1(root));
    		assertEquals(5, obj.minDepth2(root));
    	}
    }

[https_leetcode.com_problems_minimum-depth-of-binary-tree]: https://leetcode.com/problems/minimum-depth-of-binary-tree/