题目

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

题目示例

例如：

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

   3/ \9  20/  \15   7

返回它的最大深度 3

解题思路

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

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

二叉树结构


type TreeNode struct {Val intLeft *TreeNodeRight *TreeNode
}

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

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

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

复杂度分析：

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

//DFS
func maxDepth(root *TreeNode) int {//如果root为nil，直接返回0if root==nil {return 0}//分别统计左节点深度、右节点深度，取最大值最后加上+1return 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直接返回0if root == nil {return 0}// 创建一个队列var stack []*TreeNode// 把根节点放入队列stack = append(stack, root)// 声明深度变量var depth int//判断队列不为nilfor len(stack) != 0 {var tmp []*TreeNodefor _, v := range stack {// 如果有左子树，就左子树入队if v.Left != nil {tmp = append(tmp, v.Left)}// 如果有右子树，就右子树入队if v.Right != nil {tmp = append(tmp, v.Right)}}//将下一层的数赋值给stack，用于下一层循环stack = tmp//遍历每层之后，深度+1depth ++}return depth
}


func maxDepthV1(root *TreeNode) int {var r intif 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 intLeft *TreeNodeRight *TreeNode
}func TestMaxDepth(t *testing.T){head := new(TreeNode)head.Val=3left:= new(TreeNode)left.Val=9head.Left=leftright:= new(TreeNode)right.Val=20left01:= new(TreeNode)left01.Val=15right.Left=left01right02:= new(TreeNode)right02.Val=7right.Right=right02head.Right=rightfmt.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，直接返回0if root==nil {return 0}//分别统计左节点深度、右节点深度，取最大值最后加上+1return 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直接返回0if root == nil {return 0}// 创建一个队列var stack []*TreeNode// 把根节点放入队列stack = append(stack, root)// 声明深度变量var depth int//判断队列不为nilfor len(stack) != 0 {var tmp []*TreeNodefor _, v := range stack {// 如果有左子树，就左子树入队if v.Left != nil {tmp = append(tmp, v.Left)}// 如果有右子树，就右子树入队if v.Right != nil {tmp = append(tmp, v.Right)}}//将下一层的数赋值给stack，用于下一层循环stack = tmp//遍历每层之后，深度+1depth ++}return depth
}