给定一棵二叉树的根节点 root ，请找出该二叉树中每一层的最大值。
示例1：
输入: root = [1,3,2,5,3,null,9]
输出: [1,3,9]
示例2：
输入: root = [1,2,3]
输出: [1,3]
提示：
二叉树的节点个数的范围是 [0,104]
-231 <= Node.val <= 231 - 1
解题思路：
1，二叉树的题都不绕简单明了，本题常见两种解法
A，广度优先遍历
B，深度优先遍历
2，广度优先遍历思路：用两个队列交替存储每一行，求出每个队列中的最大值即可。
3，深度优先遍历：深度优先一般是递归解，每次递归的时候记录当前访问的深度，递归过程中对相同深度的取最大值。
代码实现：
广度优先遍历：
代码语言：javascript复制/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func largestValues(root *TreeNode) (r []int ){
if root==nil{
return []int{}
}
var q1,q2 []*TreeNode
q1=append(q1,root)
for len(q1)>0 {
v:= q1[0].Val
for len(q1)>0{
h:=q1[0]
q1=q1[1:]
if h.Val > v {
v= h.Val
}
if h.Left!=nil{
q2=append(q2,h.Left)
}
if h.Right!=nil{
q2=append(q2,h.Right)
}
}
r=append(r,v)
if len(q2)>0{
v:=q2[0].Val
for len(q2)>0{
h:=q2[0]
q2=q2[1:]
if h.Val>v{
v=h.Val
}
if h.Left!=nil{
q1=append(q1,h.Left)
}
if h.Right!=nil{
q1=append(q1,h.Right)
}
}
r=append(r,v)
}
}
return r
}深度优先遍历
代码语言：javascript复制/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func largestValues(root *TreeNode) (r []int ){
var dfs func(root*TreeNode,depth int)
dfs=func(root*TreeNode,depth int){
if root==nil{
return
}
if len(r)==depth{
r=append(r,root.Val)
}else{
if root.Val>r[depth]{
r[depth]=root.Val
}
}
dfs(root.Left,depth 1)
dfs(root.Right,depth 1)
}
dfs(root,0)
return r
}
