Java Queue in 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.

Solution:

The problem itself is not difficult at all. I would like to summarize the usage of queue in java.

Unlike Stack<E> which is can be used directly(empty(), peek(), pop(), push(E item), search(Object) 0), Queue<E>  (isEmpty(), add()/offer(), remove()/poll(), peek()/element()) is an interface in java.

Simply use LinkedList<E> because LinkedList has methods to support queue behavior and it implements the Queue interface, so a LinkedList can be used as a Queue implmentation by upcasting a LinkedList to a Queue, i.e., 

Queue<TreeNode> queue = LinkedList<TreeNode>();

For this problem, use BFS and an special node to indicate the end of a level (nullNode). The code passed leetcode with only one try.

	public int minDepth(TreeNode root) {
	if(root == null) return 0;
	Queue<TreeNode> llq = new LinkedList<TreeNode>();
	TreeNode nullNode = new TreeNode(0xFFFF);
	int level = 1;
	llq.add(root);
	llq.add(nullNode);
	while(!llq.isEmpty()){
	TreeNode node = llq.poll();
	if(node == nullNode){
	level++;
	llq.add(nullNode);
	}
	else{
	if(node.left == null && node.right == null)
	return level;
	if(node.left != null)
	llq.add(node.left);
	if(node.right != null)
	llq.add(node.right);
	}
	}
	return level;
	}

view raw gistfile1.java hosted with ❤ by GitHub

The most simple method to solve this problem is using recursion, as follows:

	public int minDepth(TreeNode root) {
	if(root == null) return 0;
	int level = 1;
	return minDeptRe(root, level);
	}
	public int minDeptRe(TreeNode root, int level){
	if(root.left == null && root.right == null)
	return level;
	int leftMinLevel=0;
	int rightMinLevel=0;
	/* if(root.left != null){//does not affect the running time
	if(root.left.left == null && root.left.right == null)
	return ++level;
	}
	if(root.right != null){
	if(root.right.left == null && root.right.right == null)
	return ++level;
	}*/
	if(root.left != null){
	leftMinLevel = minDeptRe(root.left, level+1);
	}
	if(root.right != null){
	rightMinLevel = minDeptRe(root.right, level+1);
	}
	if(leftMinLevel==0) return rightMinLevel;
	if(rightMinLevel==0) return leftMinLevel;
	return Math.min(leftMinLevel, rightMinLevel);
	};

view raw gistfile1.java hosted with ❤ by GitHub