FilesExpand file tree

 master

/

MinimumDepthOfBinaryTree.cpp

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

37 lines (34 loc) · 969 Bytes

 master

/

MinimumDepthOfBinaryTree.cpp

Copy path

Top

File metadata and controls

• Code
• Blame

37 lines (34 loc) · 969 Bytes

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

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

/**

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.

*/

/**

* Definition for binary tree

* struct TreeNode {

* int val;

* TreeNode *left;

* TreeNode *right;

* TreeNode(int x) : val(x), left(NULL), right(NULL) {}

* };

*/

class Solution {

public:

int minDepth(TreeNode *root) {

if (!root) return 0;

queue<pair<TreeNode*, int> > q;

q.push(make_pair(root, 1));

while (! q.empty()) {

pair<TreeNode*, int> top = q.front();

TreeNode* node = top.first;

if (!node->left && !node->right) return top.second;

q.pop();

if (node->left) {

q.push(make_pair(node->left, top.second +1));

}

if (node->right) {

q.push(make_pair(node->right, top.second +1));

}

}

}

};