LeetCode111.二叉树的最小深度

题目

深度优先搜索

 1 class Solution {
 2 public:
 3     int minDepth(TreeNode* root) {
 4         if(root == NULL) return 0;
 5         if(root->left == NULL) return minDepth(root->right)+1;
 6         if(root->right == NULL) return minDepth(root->left)+1;
 7         return min(minDepth(root->left),minDepth(root->right)) + 1;
 8     }
 9     
10 };

广度优先搜索

 1 class Solution {
 2 public:
 3     int minDepth(TreeNode* root) {
 4         if(root == NULL) return 0;
 5         
 6         queue<pair<TreeNode* ,int>>que;
 7         que.emplace(root,1);
 8         while(!que.empty()){
 9             TreeNode* node = que.front().first;
10             int depth = que.front().second;
11             que.pop();
12             if(node->left == NULL && node->right == NULL) return depth;
13             if(node->left != NULL) que.emplace(node->left,depth+1);
14             if(node->right != NULL) que.emplace(node->right,depth+1);
15         }
16         return 0;
17     }
18     
19 };