LeetCode 111

题目描述

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

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

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

示例:

给定二叉树 [3,9,20,null,null,15,7],
3
/
9 20
/
15 7
返回它的最小深度 2.

题目分析

• 宽度优先遍历（BFS）借助队列，最先到达的叶子节点一定是最小深度上的叶子节点。
• 深度优先遍历（DFS）需要遍历根节点到所有叶子节点之间的路径，然后从中选取最小深度。

代码

BFS (c++)

int minDepth(TreeNode* root) {
        if (root == NULL) return 0;
        queue<pair<TreeNode*, int>>nodes;
        nodes.emplace(root,1);
        
        while(!nodes.empty()){
            root = nodes.front().first;
            int depth = nodes.front().second;
            nodes.pop();
            if (!root->left && !root->right){
                return depth;
            }
            if(root->left){
                nodes.emplace(root->left, depth+1);
            }
            if(root->right){
                nodes.emplace(root->right, depth+1);
            }
        }
        return 0;
    }

时间复杂度：O(N) N是节点的数量。
空间复杂度：队列的容量最大为树的节点数量，即O(N)。

DFS (python)

class Solution:
    import copy
    def minDepth(self, root: TreeNode) -> int:
        res= []
        if not root:
            return 0;
        def dfs(root, depth):
            if not root.left and not root.right:
                res.append(copy.deepcopy(depth)+1);
                return
            if root.left:
                dfs(root.left, depth+1)
            if root.right:
                dfs(root.right, depth+1)
        dfs(root, 0)
        return min(res)

时间复杂度：O(N)：N是节点的个数。
空间复杂度：O(H)：H是树的高度。最坏情况是二叉树为单链表状时，空间复杂度为O(N)，平均情况为树的高度O(H) = O(logN)