用 Golang 实现给定一个二叉树,找出其最大深度。二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
说明: 叶子节点是指没有子节点的节点。
给定二叉树 [3,9,20,null,null,15,7], 3 / \ 9 20 / \ 15 7 返回它的最大深度 3 。
package main
import (
"fmt"
)
type TreeNode struct {
Val int
Left *TreeNode
Right *TreeNode
}
func maxDepth(root *TreeNode) int {
if root == nil {
return 0
}
n1 := maxDepth(root.Left)
n2 := maxDepth(root.Right)
return max(n1, n2) + 1
}
func max(x, y int) int {
if x < y {
return y
}
return x
}
func main() {
fmt.Println("嗨客网(www.haicoder.net)")
node5 := &TreeNode{
Val:7,
Left:nil,
Right:nil,
}
node4 := &TreeNode{
Val:15,
Left:nil,
Right:nil,
}
node3 := &TreeNode{
Val:20,
Left:node4,
Right:node5,
}
node2 := &TreeNode{
Val:9,
Left:nil,
Right:nil,
}
node1 := &TreeNode{
Val:3,
Left:node2,
Right:node3,
}
fmt.Println(maxDepth(node1))
}
程序运行后,控制台输出如下:
我们输入了测试用例,输出了正确结果。