Maximum Depth of Binary Tree

Question: 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.

Note: A leaf is a node with no children.

You may view the full question here.

Approach 1: Clearly this question requires a BFS approach. Here’s the first shot at it —

//Approach 1:
//Runtime: 2ms
//Memory usage: 38.6MB
/**
 * 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) {
        Stack<TreeNode> stack = new Stack();
        int count = 0;
        if(root!=null){
            count=1;
            stack.push(root);
        }
        while(!stack.isEmpty()){
            Stack<TreeNode> level = new Stack();
            while(!stack.isEmpty()){
                TreeNode curr = stack.pop();
                if(curr.left!=null)
                level.push(curr.left);
                if(curr.right!=null)
                level.push(curr.right);
            }
            if(!level.isEmpty()){
                stack = level;
                count++;
            }
        }
        return count;
    }
}

Find more posts here.

Cheers & Chao!