LeetCode 111. 二叉树的最小深度

Categories:

Tags:

题目描述
思路分析
参考代码

题目描述

✅ 111. 二叉树的最小深度

思路分析

层序遍历

参考代码

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
	}

	// 左右子树都不为空，返回较小深度 + 1
	left := minDepth(root.Left)
	right := minDepth(root.Right)

	return min(left, right) + 1
}

func minDepth(root *TreeNode) int {
	if root == nil {
		return 0
	}

	queue := []*TreeNode{root}
	depth := 1

	for len(queue) > 0 {
		size := len(queue)
		for i := 0; i < size; i++ {
			cur := queue[0]
			queue = queue[1:]

			// 遇到叶子节点，返回当前深度
			if cur.Left == nil && cur.Right == nil {
				return depth
			}

			if cur.Left != nil {
				queue = append(queue, cur.Left)
			}
			if cur.Right != nil {
				queue = append(queue, cur.Right)
			}
		}
		depth++
	}

	return depth
}

➡️ 点击查看 Java 题解

write your code here

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2024/76438130