Golang 二叉树系列【二叉树深度】

题目

输入一棵二叉树的根节点，求该树的深度。从根节点到叶节点依次经过的节点（含根、叶节点）形成树的一条路径，最长路径的长度为树的深度。

题目示例

例如：

给定二叉树 [3,9,20,null,null,15,7]

返回它的最大深度 3

解题思路

可以利用深度优先搜索（DFS）、广度优先搜索（BFS）

常见的 DFS（Deep First Search）
- 先序遍历（根左右）、中序遍历（左根右）、后序遍历（左右根）
常见的 BFS （Breath First Search）
- 层序遍历（即按层遍历）

二叉树结构


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

第一种实现-深度优先搜索（DFS）

解题公式：【最核心部分】

max(maxDepth(root.Left),maxDepth(root.Right))+1

复杂度分析：

时间复杂度 O(N) ： N 为树的节点数量，计算树的深度需要遍历所有节点。
空间复杂度 O(N)：最差情况下（当树退化为链表时），递归深度可达到 N 。

//DFS
func maxDepth(root *TreeNode) int {
	//如果root为nil，直接返回0
	if root==nil {
		return 0
	}
	//分别统计左节点深度、右节点深度，取最大值最后加上+1
	return max(maxDepth(root.Left),maxDepth(root.Right))+1
}

//获取最大值
func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

第二种实现-广度优先搜索 BFS

解题思路：

遍历一层，则计数器 +1+1 ，直到遍历完成，则可得到树的深度。

复杂度分析：

时间复杂度 O(N)
空间复杂度 O(N)

//BFS
func maxDepthV2(root *TreeNode) int {
	// 根节点如果为0直接返回0
	if root == nil {
		return 0
	}
	// 创建一个队列
	var stack []*TreeNode
	// 把根节点放入队列
	stack = append(stack, root)
	// 声明深度变量
	var depth int
	//判断队列不为nil
	for len(stack) != 0 {
		var tmp []*TreeNode
		for _, v := range stack {
			// 如果有左子树，就左子树入队
			if v.Left != nil {
				tmp = append(tmp, v.Left)
			}
			// 如果有右子树，就右子树入队
			if v.Right != nil {
				tmp = append(tmp, v.Right)
			}
		}
		//将下一层的数赋值给stack，用于下一层循环
		stack = tmp
		//遍历每层之后，深度+1
		depth ++
	}
	return depth
}


func maxDepthV1(root *TreeNode) int {
	var r int
	if root==nil{
		return  r
	}
	lt:=list.New()
	lt.PushBack(root)
	for lt.Len()>0{
		ln:=lt.Len()
		for i := 0; i < ln; i++ {
			node:=lt.Remove(lt.Front()).(*TreeNode)
			if node.Right!=nil{
				lt.PushBack(node.Right)
			}
			if node.Left!=nil{
				lt.PushBack(node.Left)
			}
		}
		r++
	}
	return r
}

Golang 解题代码


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

func TestMaxDepth(t *testing.T){
	head := new(TreeNode)
	head.Val=3
	left:= new(TreeNode)
	left.Val=9
	head.Left=left
	right:= new(TreeNode)
	right.Val=20
	left01:= new(TreeNode)
	left01.Val=15
	right.Left=left01
	right02:= new(TreeNode)
	right02.Val=7
	right.Right=right02
	head.Right=right
	fmt.Printf("depth: %v",maxDepth(head))
	fmt.Printf("\n")
	fmt.Printf("depth: %v",maxDepthV2(head))
	fmt.Printf("\n")
}
//DFS
func maxDepth(root *TreeNode) int {
	//如果root为nil，直接返回0
	if root==nil {
		return 0
	}
	//分别统计左节点深度、右节点深度，取最大值最后加上+1
	return max(maxDepth(root.Left),maxDepth(root.Right))+1
}

//获取最大值
func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

//BFS
func maxDepthV2(root *TreeNode) int {
	// 根节点如果为0直接返回0
	if root == nil {
		return 0
	}
	// 创建一个队列
	var stack []*TreeNode
	// 把根节点放入队列
	stack = append(stack, root)
	// 声明深度变量
	var depth int
	//判断队列不为nil
	for len(stack) != 0 {
		var tmp []*TreeNode
		for _, v := range stack {
			// 如果有左子树，就左子树入队
			if v.Left != nil {
				tmp = append(tmp, v.Left)
			}
			// 如果有右子树，就右子树入队
			if v.Right != nil {
				tmp = append(tmp, v.Right)
			}
		}
		//将下一层的数赋值给stack，用于下一层循环
		stack = tmp
		//遍历每层之后，深度+1
		depth ++
	}
	return depth
}

结果验证