LeetCode 111

題目描述

給定一個(gè)二叉樹(shù)，找出其最小深度。

最小深度是從根節(jié)點(diǎn)到最近葉子節(jié)點(diǎn)的最短路徑上的節(jié)點(diǎn)數(shù)量。

說(shuō)明: 葉子節(jié)點(diǎn)是指沒(méi)有子節(jié)點(diǎn)的節(jié)點(diǎn)。

示例:

給定二叉樹(shù) [3,9,20,null,null,15,7],
3
/
9 20
/
15 7
返回它的最小深度 2.

題目分析

• 寬度優(yōu)先遍歷（BFS）借助隊(duì)列，最先到達(dá)的葉子節(jié)點(diǎn)一定是最小深度上的葉子節(jié)點(diǎn)。
• 深度優(yōu)先遍歷（DFS）需要遍歷根節(jié)點(diǎn)到所有葉子節(jié)點(diǎn)之間的路徑，然后從中選取最小深度。

代碼

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;
    }

時(shí)間復(fù)雜度：O(N) N是節(jié)點(diǎn)的數(shù)量。
空間復(fù)雜度：隊(duì)列的容量最大為樹(shù)的節(jié)點(diǎn)數(shù)量，即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)

時(shí)間復(fù)雜度：O(N)：N是節(jié)點(diǎn)的個(gè)數(shù)。
空間復(fù)雜度：O(H)：H是樹(shù)的高度。最壞情況是二叉樹(shù)為單鏈表狀時(shí)，空間復(fù)雜度為O(N)，平均情況為樹(shù)的高度O(H) = O(logN)