MaximumDepthOfBinaryTree.java

/**
 * Given a binary tree, find its maximum depth.
 * 
 * The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.
 */

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


public class MaximumDepthOfBinaryTree {
 public int maxDepth(TreeNode root) {
 if (root == null) return 0;
 	int ret = 1;
 	int currentLevel = 1;
 	int nextLevel = 0;
 	Queue<TreeNode> queue = new LinkedList<TreeNode>();
 	queue.add(root);
 	while (!queue.isEmpty()) {
 		TreeNode node = queue.remove();
 		currentLevel--;
 		if (node.left != null) {
 			queue.add(root.left);
 			nextLevel++;
 		}
 		if (node.right != null) {
 			queue.add(root.right);
 			nextLevel++;
 		}
 		if (currentLevel == 0) {
 			if (nextLevel != 0) {
 				ret++;
 			}
 			currentLevel = nextLevel;
 			nextLevel = 0;
 		}
 	}
 	return ret;
 }
}