LeetCode 0111.二叉树的最小深度【Go】

二叉树的最小深度

LeetCode111. 二叉树的最小深度

题目描述

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

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

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

思路

本题使用层序遍历的方式来解决，只有当左右孩子都为空的时候，才说明找到了最小深度。如果其中一个孩子为空则不是最小深度。

代码 Go

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

func minDepth(root *TreeNode) int {
	if root == nil {
		// 根节点为空
		return 0
	}
	// 用切片模拟队列
	queue := make([]*TreeNode, 0)
	// 根节点入队
	queue = append(queue, root)
	// 最小深度初始化为1
	minDepth := 1
	// 遍历二叉树
	for len(queue) > 0 {
		// 记录当前层节点数
		l := len(queue)
		// 遍历一层
		for i := 0; i < l; i++ {
			// 当前节点没有子节点,返回当前深度
			if queue[0].Left == nil && queue[0].Right == nil {
				return minDepth
			}
			// 若当前节点有子节点,则入队
			if queue[0].Left != nil {
				// 左子节点入队
				queue = append(queue, queue[0].Left)
			}
			if queue[0].Right != nil {
				// 右子节点入队
				queue = append(queue, queue[0].Right)
			}
			// 当前节点出队
			queue = queue[1:]
		}
		// 该层节点都有子节点,最小深度+1
		minDepth++
	}
	return minDepth
}

Link

GitHub