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
}

复制