image.png

思路1：（DFS）

  • 利用递归的结构，最小层次要么在左子树上产生，要么在右子树上产生
  • 这种做法是比较慢的
    代码如下：
  1. /**
  2.  * Definition for a binary tree node.
  3.  * struct TreeNode {
  4.  *     int val;
  5.  *     TreeNode *left;
  6.  *     TreeNode *right;
  7.  *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
  8.  *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  9.  *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
  10.  * };
  11.  */
  12. class Solution {
  13. public:
  14.     int minDepth(TreeNode* root) {
  15.         if (root == nullptr) {
  16.             return 0;
  17.         }
  18.         int left = minDepth(root->left);
  19.         int right = minDepth(root->right);
  20.         return (left == 0 || right == 0) ? left + right + 1 : min(left, right) + 1;
  21.     }
  22. };

思路2：（BFS）

  • 利用BFS的好处在于，可以不用读完整棵树
  • 层次遍历，遍历到第一个叶子节点直接返回
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int minDepth(TreeNode* root) {
        int min_depth = 0;
        if (!root) {
            return 0;
        }

        queue<TreeNode*> q;
        q.push(root);

        int count_level = 0;
        while (!q.empty()) {
            int cur_level_size = q.size();
            count_level++;
            for (int i = 0; i < cur_level_size; ++i) {
                TreeNode* cur_node = q.front();
                q.pop();

                if (!cur_node->left && !cur_node->right) {
                    min_depth = count_level;
                    return min_depth;
                } 
                if (cur_node->left) q.push(cur_node->left);
                if (cur_node->right) q.push(cur_node->right);
            }
        }

        return min_depth;
    }
};