golang刷leetcode: 在每个树行中找最大值-轻识

给定一棵二叉树的根节点 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 []*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}

深度优先遍历

/** * 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}

推荐阅读

golang刷leetcode: 卖木头块

福利

我为大家整理了一份从入门到进阶的Go学习资料礼包，包含学习建议：入门看什么，进阶看什么。关注公众号「polarisxu」，回复 ebook 获取；还可以回复「进群」，和数万 Gopher 交流学习。