LeetCode 111. Minimum Depth of Binary Tree

LeetCode in Java (8 Part Series)

1 LeetCode 20. Valid Parentheses
2 LeetCode 7. Reverse Integer
… 4 more parts…
3 LeetCode 281. Move Zeros
4 LeetCode 238. Product of Array Except Self
5 LeetCode 31. Next Permutation
6 LeetCode 98. Validate Binary Search Tree
7 LeetCode 111. Minimum Depth of Binary Tree
8 LeetCode in Java: 209

public class Solution {
    public int minDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }

        Queue<TreeNode> q = new LinkedList<>();
        TreeNode rightMost = root;
        q.add(root);
        int depth = 1;
        while (!q.isEmpty()) {
            TreeNode node = q.poll();
            if (node.left == null && node.right == null) {
                break;
            }
            if (node.left != null) {
                q.add(node.left);
            }
            if (node.right != null) {
                q.add(node.right);
            }
            if (node == rightMost) {
                depth++;
                rightMost = (node.right != null) ? node.right : node.left;
            }
        }

        return depth;
    }
}

We use BFS to solve this problem. We add nodes at the same level to a queue q. We iterate through each of the nodes. When we encounter a leaf node, we stop and return depth (the minimum depth). After iterating all the nodes at the same level, we still cannot find a leaf node, we increment depth by 1 then repeat the above process for the nodes at the next level. We can use DFS as well. However, BFS outperforms DFS on highly unbalanced trees since it terminates once it reaches the first leaf node.

Time Complexity: O(n)

Extra Space: O(1)

LeetCode in Java (8 Part Series)

1 LeetCode 20. Valid Parentheses
2 LeetCode 7. Reverse Integer
… 4 more parts…
3 LeetCode 281. Move Zeros
4 LeetCode 238. Product of Array Except Self
5 LeetCode 31. Next Permutation
6 LeetCode 98. Validate Binary Search Tree
7 LeetCode 111. Minimum Depth of Binary Tree
8 LeetCode in Java: 209

原文链接：LeetCode 111. Minimum Depth of Binary Tree