-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathminimum_depth_of_binary_tree.cpp
More file actions
133 lines (108 loc) · 2.7 KB
/
Copy pathminimum_depth_of_binary_tree.cpp
File metadata and controls
133 lines (108 loc) · 2.7 KB
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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
/*
Minimum Depth of Binary Tree
Given a binary tree, find its minimum depth.
The minimum depth is the number of nodes along the shortest path
from the root node down to the nearest leaf node.
*/
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
//Definition for binary tree
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) :
val(x), left(NULL), right(NULL)
{
}
};
// recursively
class Solution
{
public:
int minDepth(TreeNode *root)
{
if (root == nullptr)
return 0;
else if (!root->left) // be careful about tree has only one child
return minDepth(root->right) + 1;
else if (!root->right)
return minDepth(root->left) + 1;
else {
int leftDepth = minDepth(root->left);
int rightDepth = minDepth(root->right);
return min(leftDepth, rightDepth) + 1;
}
}
};
// unrecursively
class Solution2
{
public:
int minDepth(TreeNode *root)
{
if (!root) return 0;
queue<TreeNode *> q;
TreeNode *cur = nullptr;
int level = 0, levelSize = 0;
q.push(root);
while (!q.empty()) {
if (levelSize == 0 ) {
levelSize = q.size();
level++;
}
cur = q.front();
q.pop();
levelSize--;
if (!cur->left && !cur->right) return level;
if (cur->left) q.push(cur->left);
if (cur->right) q.push(cur->right);
}
return level;
}
};
// recursively
class Solution3
{
private:
void minDepth(TreeNode *t, int level, int &depth)
{
if (t) {
if (!t->left && !t->right) {
depth = min(depth, level);
}
minDepth(t->left, level + 1, depth);
minDepth(t->right, level + 1, depth);
}
}
public:
int minDepth(TreeNode *root)
{
if (!root) return 0;
int depth = INT_MAX;
minDepth(root, 1, depth);
return depth;
}
};
int main(int argc, char *argv[])
{
Solution sol;
Solution2 sol2;
Solution3 sol3;
TreeNode *root = new TreeNode(3);
root->left = new TreeNode(9);
root->right = new TreeNode(20);
root->right->left = new TreeNode(15);
root->right->right = new TreeNode(7);
TreeNode *root2 = new TreeNode(1); //
root2->left = new TreeNode(2);
cout << sol.minDepth(root) << endl;
cout << sol.minDepth(root2) << endl;
cout << sol2.minDepth(root) << endl;
cout << sol2.minDepth(root2) << endl;
cout << sol3.minDepth(root) << endl;
cout << sol3.minDepth(root2) << endl;
return 0;
}