LeetCode - Algorithms - 104. Maximum Depth of Binary Tree

Problem

104. Maximum Depth of Binary Tree

Java

Depth-first Search - Recursion

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    private int recur(TreeNode node, int h) {
        if (node != null)
            return Math.max(recur(node.left, h + 1), recur(node.right, h + 1));
        else
            return h;
    }
    
    public int maxDepth(TreeNode root) {
        return recur(root, 0);
    }
}

Submission Detail

  • 39 / 39 test cases passed.
  • Runtime: 0 ms, faster than 100.00% of Java online submissions for Maximum Depth of Binary Tree.
  • Memory Usage: 39 MB, less than 49.45% of Java online submissions for Maximum Depth of Binary Tree.

DFS

© Finding max depth of binary tree without recursion

This variant uses two stacks, one for additional nodes to explore (wq) and one always containing the current path from the root (path). When we see the same node on the top of both stacks it means we’ve explored everything below it and can pop it. This is the time to update the tree depth too.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public int maxDepth(TreeNode root) {
        int depth = 0;
        if (root == null) return 0;
        Deque<TreeNode> wq = new LinkedList<TreeNode>();
        Deque<TreeNode> path = new LinkedList<TreeNode>();

        wq.push(root);
        while (!wq.isEmpty()) {
            root = wq.peek();
            if (!path.isEmpty() && root == path.peek()) {
                if (path.size() > depth)
                    depth = path.size();
                path.pop();
                wq.pop();
            } else {
                path.push(root);
                if (root.right != null)
                    wq.push(root.right);
                if (root.left != null)
                    wq.push(root.left);
            }
        }

        return depth;
    }
}

Submission Detail

  • 39 / 39 test cases passed.
  • Runtime: 3 ms, faster than 5.14% of Java online submissions for Maximum Depth of Binary Tree.
  • Memory Usage: 38.6 MB, less than 96.88% of Java online submissions for Maximum Depth of Binary Tree.

BFS

© Day 39— Max Depth of Binary Tree Using BFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public int maxDepth(TreeNode root) {
        int h = 0;
        if (root == null) return 0;
        TreeNode node = null;
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                node = queue.poll();
                if (node.left != null) queue.add(node.left);
                if (node.right != null) queue.add(node.right);
            }
            h++;
        }
        return h;
    }
}

Submission Detail

  • 39 / 39 test cases passed.
  • Runtime: 1 ms, faster than 14.50% of Java online submissions for Maximum Depth of Binary Tree.
  • Memory Usage: 38.6 MB, less than 92.61% of Java online submissions for Maximum Depth of Binary Tree.