111. Minimum Depth of Binary Tree - cocoder39/coco39_LC GitHub Wiki

111. Minimum Depth of Binary Tree

The minimum depth is defined as the number of nodes along the shortest path from the root node to a leaf node. the min depth of tree [1, 2, #] is 2 rather than 1, which is different from 104. Maximum Depth of Binary Tree.

Solution 1: dfs. time complexity is O(n) and space complexity is O(h) where h is height of tree, h != log n if tree is skewed.

int minDepth(TreeNode* root) {
        if (! root) {
            return 0;
        } else if (! root->left) {
            return 1 + minDepth(root->right);
        } else if (! root->right) {
            return 1 + minDepth(root->left);
        } 
        return 1 + min(minDepth(root->left), minDepth(root->right));
    }

Solution 2: terminate bfs when finding out a leave node. bfs outperforms dfs when tree is skewed. time complexity is O(n) and space complexity is O(w) where w is width of the tree

int minDepth(TreeNode* root) {
        queue<TreeNode*> que;
        if (root) {
            que.push(root);
        }
        int depth = 0;
        while (! que.empty()) {
            depth++;
            int sz = que.size();
            for (int i = 0; i < sz; i++) {
                TreeNode* node = que.front();
                que.pop();
                if (! node->left && ! node->right) { // leave node
                    return depth;
                }
                if (node->left) {
                    que.push(node->left);
                }  
                if (node->right) {
                    que.push(node->right);
                }
            }
        }
        return depth;
    }
⚠️ **GitHub.com Fallback** ⚠️