[2018-Interview] Maximum Depth of Binary Tree

Original question: https://leetcode.com/problems/maximum-depth-of-binary-tree/description/

My answer: we can have 2 solutions: recursive and iterative. Solution 2 uses 2 queues to keep track of current level nodes and next level nodes.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public int maxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        // Solution 1: recursive
//         int leftMaxDepth = maxDepth(root.left);
//         int rightMaxDepth = maxDepth(root.right);
//         return (Math.max(leftMaxDepth, rightMaxDepth) + 1);
        
        // Solution 2: iterative
        int maxDepth = 1;
        LinkedList<TreeNode> currentLevel = new LinkedList<TreeNode>();
        LinkedList<TreeNode> nextLevel = new LinkedList<TreeNode>();
        currentLevel.add(root);
        while(true) {
            while (!currentLevel.isEmpty()) {
                TreeNode currentNode = currentLevel.removeFirst();
                if (currentNode.left != null) {
                    nextLevel.add(currentNode.left);
                }
                if (currentNode.right != null) {
                    nextLevel.add(currentNode.right);
                }
            }
            if (nextLevel.isEmpty()) {
                break;
            }
            maxDepth ++;
            currentLevel.addAll(nextLevel);
            nextLevel = new LinkedList<TreeNode>();
        }
        return maxDepth;
    }
}