This problem is just similar to Minimum Depth of Binary Tree.
The first solution also uses recursion (not sure whether it can be called DFS).
1 class Solution { 2 public: 3 int minDepth(TreeNode* root) { 4 if (!root) return 0; 5 if (!(root -> left)) return minDepth(root -> right) + 1; 6 if (!(root -> right)) return minDepth(root -> left) + 1; 7 return min(minDepth(root -> left), minDepth(root -> right)) + 1; 8 } 9 };
Well, the above code may be compressed into 1 line using nested conditional statements. But I tend to keep its logic clear.
The second solution adopts a level-order traversal (BFS) with a queue. We use two bool variables lt and rt to detect leaf nodes.
1 class Solution { 2 public: 3 int minDepth(TreeNode* root) { 4 int depth = 0; 5 if (!root) return depth; 6 queue<TreeNode*> level; 7 level.push(root); 8 while (!level.empty()) { 9 depth++; 10 int n = level.size(); 11 for (int i = 0; i < n; i++) { 12 bool lt = true, rt = true; 13 TreeNode* node = level.front(); 14 level.pop(); 15 if (node -> left) level.push(node -> left); 16 else lt = false; 17 if (node -> right) level.push(node -> right); 18 else rt = false; 19 if (!lt && !rt) return depth; 20 } 21 } 22 } 23 };
