111. 二叉树的最小深度

题目描述

输入二叉树的根节点 root，求它的最小深度。

最小深度指：从根出发走到离根最近的叶子节点，这条路径上的节点个数（含根和该叶子）。叶子节点是左右孩子都为空的节点。

注意只有一个孩子的节点不是叶子，不能在那里停下。空树的最小深度为 0。树用层序数组表示，null 代表空位。

示例 1

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

解释：最近的叶子是 9，路径 3 -> 9 含 2 个节点。

示例 2

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

解释：树退化成一条向右的链，唯一的叶子是 6，路径上共 5 个节点。

数据范围

节点总数在 [0, 10^5] 之间。
-1000 <= Node.val <= 1000

解题思路：广度优先搜索

按层 BFS，队列中同时记录节点和它的深度。BFS 按深度从小到大访问节点，所以第一次弹出叶子时，它的深度就是最小深度，可以立刻返回，不必遍历整棵树。

为什么正确

队列中的深度单调不减；弹出一个深度为 d 的节点时，所有深度小于 d 的节点都已弹出且不是叶子。

复杂度分析

时间 O(n)，最坏遍历所有节点；空间 O(n)。

易错点

不能照搬最大深度写成 min(左, 右) + 1。当一侧为空时，空的一侧没有叶子，不能被当作深度 0。例如 [2,null,3] 的答案是 2 而不是 1。

参考代码

Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。

class Solution:
    def minDepth(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 0
        q = collections.deque([(root, 1)])
        while q:
            node, d = q.popleft()
            if not node.left and not node.right:
                return d
            if node.left:
                q.append((node.left, d + 1))
            if node.right:
                q.append((node.right, d + 1))

class Solution {
    public int minDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        Deque<Object[]> q = new ArrayDeque<>();
        q.offer(new Object[]{root, 1});
        while (!q.isEmpty()) {
            Object[] cur = q.poll();
            TreeNode node = (TreeNode) cur[0];
            int d = (int) cur[1];
            if (node.left == null && node.right == null) {
                return d;
            }
            if (node.left != null) {
                q.offer(new Object[]{node.left, d + 1});
            }
            if (node.right != null) {
                q.offer(new Object[]{node.right, d + 1});
            }
        }
        return 0;
    }
}

class Solution {
public:
    int minDepth(TreeNode* root) {
        if (!root) {
            return 0;
        }
        queue<pair<TreeNode*, int>> q;
        q.push({root, 1});
        while (!q.empty()) {
            auto [node, d] = q.front();
            q.pop();
            if (!node->left && !node->right) {
                return d;
            }
            if (node->left) {
                q.push({node->left, d + 1});
            }
            if (node->right) {
                q.push({node->right, d + 1});
            }
        }
        return 0;
    }
};

func minDepth(root *TreeNode) int {
	if root == nil {
		return 0
	}
	type item struct {
		node *TreeNode
		d    int
	}
	q := []item{{root, 1}}
	for len(q) > 0 {
		cur := q[0]
		q = q[1:]
		node, d := cur.node, cur.d
		if node.Left == nil && node.Right == nil {
			return d
		}
		if node.Left != nil {
			q = append(q, item{node.Left, d + 1})
		}
		if node.Right != nil {
			q = append(q, item{node.Right, d + 1})
		}
	}
	return 0
}

var minDepth = function(root) {
    if (!root) {
        return 0;
    }
    const q = [[root, 1]];
    for (let h = 0; h < q.length; h++) {
        const [node, d] = q[h];
        if (!node.left && !node.right) {
            return d;
        }
        if (node.left) {
            q.push([node.left, d + 1]);
        }
        if (node.right) {
            q.push([node.right, d + 1]);
        }
    }
    return 0;
};

function minDepth(root: TreeNode | null): number {
    if (!root) {
        return 0;
    }
    const q: [TreeNode, number][] = [[root, 1]];
    for (let h = 0; h < q.length; h++) {
        const [node, d] = q[h];
        if (!node.left && !node.right) {
            return d;
        }
        if (node.left) {
            q.push([node.left, d + 1]);
        }
        if (node.right) {
            q.push([node.right, d + 1]);
        }
    }
    return 0;
}

载入编辑器，自己跑一遍 →

其他解法

广度优先搜索遇到最浅的叶子就返回，通常访问节点更少；深度优先搜索代码更短，空间随树高变化。

解法 2：深度优先搜索时间 O(n)，空间 O(h)

空树返回 0，叶子返回 1。只有一侧子树时，只能走那一侧，返回它的最小深度加一。两侧都有时，取较小值加一。

写法和最大深度对称，但要注意单侧为空不能算作深度 0。它必须遍历整棵树；广度优先搜索遇到第一个叶子就停。

import sys

class Solution:
    def minDepth(self, root):
        sys.setrecursionlimit(10000)
        if not root:
            return 0
        if not root.left:
            return self.minDepth(root.right) + 1
        if not root.right:
            return self.minDepth(root.left) + 1
        return min(self.minDepth(root.left), self.minDepth(root.right)) + 1

class Solution {
    public int minDepth(TreeNode root) {
        if (root == null) return 0;
        if (root.left == null) return minDepth(root.right) + 1;
        if (root.right == null) return minDepth(root.left) + 1;
        return Math.min(minDepth(root.left), minDepth(root.right)) + 1;
    }
}

class Solution {
public:
    int minDepth(TreeNode* root) {
        if (!root) return 0;
        if (!root->left) return minDepth(root->right) + 1;
        if (!root->right) return minDepth(root->left) + 1;
        return min(minDepth(root->left), minDepth(root->right)) + 1;
    }
};

func minDepth(root *TreeNode) int {
	if root == nil {
		return 0
	}
	if root.Left == nil {
		return minDepth(root.Right) + 1
	}
	if root.Right == nil {
		return minDepth(root.Left) + 1
	}
	return min(minDepth(root.Left), minDepth(root.Right)) + 1
}

var minDepth = function(root) {
    if (!root) return 0;
    if (!root.left) return minDepth(root.right) + 1;
    if (!root.right) return minDepth(root.left) + 1;
    return Math.min(minDepth(root.left), minDepth(root.right)) + 1;
};

function minDepth(root: TreeNode | null): number {
    if (!root) return 0;
    if (!root.left) return minDepth(root.right) + 1;
    if (!root.right) return minDepth(root.left) + 1;
    return Math.min(minDepth(root.left), minDepth(root.right)) + 1;
};

二叉树专题的其他题目

查看二叉树全部题目 →