给定一棵二叉树的根节点 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，深度优先遍历：深度优先一般是递归解，每次递归的时候记录当前访问的深度，递归过程中对相同深度的取最大值。
代码实现：
广度优先遍历：
/*** 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 []*TreeNodeq1=append(q1,root)for len(q1)>0 {v:= q1[0].Valfor 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].Valfor 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}
深度优先遍历
/*** 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}
推荐阅读
文章来源: http://mp.weixin.qq.com/s?__biz=MzAxMTA4Njc0OQ==&mid=2651453211&idx=2&sn=9aa89f42b2e45d927b5200814ae003c7&chksm=80bb29e9b7cca0ffb71e462f069a5837fe9dd2c4930348095c2cc62627f0dbfef8139ca82465#rd
如有侵权请联系:admin#unsafe.sh
如有侵权请联系:admin#unsafe.sh