题目描述

给定一个二叉树，找出其最小深度。
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
说明: 叶子节点是指没有子节点的节点。

样例

给定二叉树 [3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7
返回它的最小深度  2.

算法1

(递归DFS) $O(n)$

遍历所有节点并记录深度，遇到叶子节点就更新一下答案。

时间复杂度

遍历所有节点，所以时间复杂度$O(n)$。

参考文献

C++ 代码

class Solution {
private:
    int res = INT_MAX;
public:
    int minDepth(TreeNode* root) {
        if (!root) return 0;
        dfs(root, 1);
        return res;
    }

    void dfs(TreeNode *root, int depth){
        if (!root) return;
        if (!root->left && !root->right){
            res = min(res, depth);
            return;
        }

        dfs(root->left, depth + 1);
        dfs(root->right, depth + 1);
    }
};

算法2

(迭代DFS) $O(n)$

用栈模拟DFS，遍历所有节点，并记录深度，每次到达叶节点，就更新答案。

时间复杂度

遍历所有节点，所以时间复杂度$O(n)$。

参考文献

C++ 代码

class Solution {
public:
    int minDepth(TreeNode* root) {
        if (!root) return 0;
        stack<pair<TreeNode *, int>> S; S.push({root, 1});
        int res = INT_MAX;

        while (!S.empty()){
            auto n_d = S.top(); S.pop();
            int cur_depth = n_d.second;
            TreeNode *node = n_d.first;
            if (!node->left && !node->right)
                res = min(res, cur_depth);

            if (node->left) S.push({node->left, cur_depth + 1});
            if (node->right) S.push({node->right, cur_depth + 1});
        }

        return res;
    }
};

算法3

(BFS层序遍历) $O(n)$

既然是求最短，那么可以联想到用BFS求解，层序遍历二叉树，遇到叶子节点，直接返回深度即可，它一定是最浅的了。

时间复杂度

遍历所有节点，所以时间复杂度$O(n)$。

参考文献

C++ 代码

class Solution {
public:
    int minDepth(TreeNode* root) {
        if (!root) return 0;
        int depth = 1;
        queue<TreeNode *> Q; Q.push(root);

        while (!Q.empty()){
            int size = Q.size();
            while (size--){
                TreeNode *node = Q.front(); Q.pop();
                if (!node->left && !node->right) return depth;
                if (node->left) Q.push(node->left);
                if (node->right) Q.push(node->right);
            }
            ++depth;
        }

        return depth;
    }
};