題目
Given a binary tree, find its maximum depth.
The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.
解題思路
層序遍歷二叉樹诫咱，每增加一層答捕，最大深度+1.
樹不能為空，二叉樹可以為空，因此最大深度可以為0.
代碼
maxDepth.go
package _104_Maximum_Depth_of_Binary_Tree
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
type TreeNode struct {
Val int
Left *TreeNode
Right *TreeNode
}
func nextDepthNode(nodeSlice []*TreeNode) (nextNodeSlice []*TreeNode) {
for _, node := range nodeSlice {
if nil != node.Left {
nextNodeSlice = append(nextNodeSlice, node.Left)
}
if nil != node.Right {
nextNodeSlice = append(nextNodeSlice, node.Right)
}
}
return nextNodeSlice
}
func MaxDepth(root *TreeNode) int {
var maxDepth int
if nil == root {
return 0
}
nextNodeSlice := []*TreeNode{root}
for ; len(nextNodeSlice) > 0; {
maxDepth++
nextNodeSlice = nextDepthNode(nextNodeSlice)
}
return maxDepth
}
測試代碼
maxDepth_test.go
package _104_Maximum_Depth_of_Binary_Tree
import "testing"
func InitNode(val int, left *TreeNode, right *TreeNode) (ret *TreeNode){
ret = new(TreeNode)
ret.Val = val
ret.Left = left
ret.Right = right
return ret
}
func TestMaxDepth(t *testing.T) {
l3_1 := InitNode(3, nil, nil)
l2_1 := InitNode(2, l3_1, nil)
root := InitNode(1, l2_1, nil)
want := 3
ret := MaxDepth(root)
if ret == want {
t.Logf("pass")
} else {
t.Errorf("fail, want %+v, get %+v", want, ret)
}
}
