题目

给定一个二叉树，找出其最小深度。

最小深度是从根节点到最近叶子节点的最短路径上的节点数量。

说明：叶子节点是指没有子节点的节点。

示例 1：
image.png

  1. 输入：root = [3,9,20,null,null,15,7]
  2. 输出：2

示例 2：

  1. 输入：root = [2,null,3,null,4,null,5,null,6]
  2. 输出：5

提示：

  • 树中节点数的范围在 [0, 10^5] 内

  • -1000 <= Node.val <= 1000

    解题方法

    BFS

    通过 BFS 由上向下层序遍历二叉树，当遇到最小深度子节点时退出搜索，返回当前深度。
    时间复杂度O(n)，空间复杂度O(n)
    C++代码：

    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.       int depth = 0;
    16.       bool state = false;
    17.       queue<TreeNode*> nodes;
    18.       if(root)    nodes.push(root);
    19.       while(nodes.size()>0) {
    20.           depth++;
    21.           int size = nodes.size();
    22.           for(int i=0; i<size; i++) {
    23.               if(!nodes.front()->left && !nodes.front()->right) {
    24.                   state = true;
    25.                   break;
    26.               }
    27.               if(nodes.front()->left)     nodes.push(nodes.front()->left);
    28.               if(nodes.front()->right)    nodes.push(nodes.front()->right);
    29.               nodes.pop();
    30.           }
    31.           if(state) break;
    32.       }
    34.       return depth;
    35.   }
    36. };

    DFS

    通过 DFS 遍历二叉树，更新最小深度。
    时间复杂度O(n)，空间复杂度O(height)（平均为O(logn)，最劣O(n)）
    C++代码：

    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.   void DFS(TreeNode* cur, int level, int &min_depth) {
    15.       if(!cur) return;
    16.       if(!cur->left && !cur->right)   min_depth = level<min_depth ? level : min_depth;
    17.       DFS(cur->left, level+1, min_depth);
    18.       DFS(cur->right, level+1, min_depth);
    19.   }
    21.   int minDepth(TreeNode* root) {
    22.       int min_depth = INT_MAX;
    23.       if(!root)   return 0;
    24.       DFS(root, 1, min_depth);
    26.       return min_depth;
    27.   }
    28. };