EEPW论坛

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.

题意：求最小路径。

方法一：递归

1. class Solution  

2. {  

3. public:  

4.     int run(TreeNode* root)  

5.     {  

6.         if (root==NULL)  

7.         {  

8.             return 0;  

9.         }  

10.   

11.         int left = run(root->left);  

12.         int right = run(root->right);  

13.           

14.         return 1 + min(left,right);  

15.     }  

16. };  

方法二：非递归，采用层次遍历，如果该层有叶子节点，那么最短depth到此为止，如果没有，继续遍历下一层

1. class Solution  

2. {  

3. public:  

4.     int run(TreeNode* root)  

5.     {  

6.         if(root==NULL)  

7.         {  

8.             return 0;  

9.         }  

10.   

11.         if (root->left == NULL && root->right == NULL)  

12.         {  

13.             return 1;  

14.         }  

15.   

16.         int depth = 0;  

17.         queue<TreeNode*> qu;  

18.         qu.push(root);  

19.   

20.         while (!qu.empty())  

21.         {  

22.             int len = qu.size();  

23.             depth++;  

24.   

25.             for (int i = 0; i<len; i++)  

26.             {  

27.                 TreeNode* cur = qu.front();  

28.                 qu.pop();  

29.                 if (cur->left == NULL && cur->right == NULL)  

30.                 {  

31.                     return depth;  

32.                 }  

33.   

34.                 if (cur->left != NULL)  

35.                 {  

36.                     qu.push(cur->left);  

37.                 }  

38.                 if (cur->right != NULL)  

39.                 {  

40.                     qu.push(cur->right);  

41.                 }  

42.             }  

43.         }  

44.   

45.     }  

46. };