[LeetCode] Minimum Depth of Binary Tree

更新时间：2022-04-14 19:24:51

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 };

上一篇 : ：[LeetCode] Add Digits下一篇 : [LeetCode] Binary Tree Paths

[LeetCode] Minimum Depth of Binary Tree

相关阅读

推荐文章