104. Maximum Depth of Binary Tree

Easy (LinkedIn, Uber, Apple, Yahoo)

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.

/**

• Definition for a binary tree node.
• public class TreeNode {
• int val;
• TreeNode left;
• TreeNode right;
• TreeNode(int x) { val = x; }
• } */

Explaination:

recursion method and iterator method

Solution 1: recusion

public class Solution {

// test case:
// root == null

public int maxDepth(TreeNode root) {
    if(root == null) {
        return 0;
    }

    int leftDepth = maxDepth(root.left);
    int rightDepth = maxDepth(root.right);
    return Math.max(leftDepth, rightDepth) + 1;
}

}

Solution 2: iterator

public class Solution {

// test case:
// root == null

public int maxDepth(TreeNode root) {
    if(root == null) {
        return 0;
    }

    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);
    int level = 0;
    int size = 1;

    while(!queue.isEmpty()) {
        TreeNode node = queue.poll();

        if(node.left != null) {
            queue.offer(node.left);
        }

        if(node.right != null) {
            queue.offer(node.right);
        }

        if(--size == 0) {
            size = queue.size();
            level++;
        }
    }

    return level;
}

}