刷题使我快乐，满脸开心.jpg

• 来源：力扣（LeetCode）
• 链接：https://leetcode.cn/problems/binary-tree-right-side-view/
• 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题目

给定一个二叉树的 根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。

示例 1:

输入: [1,2,3,null,5,null,4]
输出: [1,3,4]

示例 2:

输入: [1,null,3]
输出: [1,3]

示例 3:

输入: []
输出: []

提示:

• 二叉树的节点个数的范围是 [0,100]
• -100 <= Node.val <= 100

思路

其实不是很能理解这个题为啥被划分为中等...

思路本质上还是遍历，只是取结果限定了一个只取每层最右侧值而已

广度优先 bfs

层序遍历就是每层节点从右往左遍历（根据使用选择的数据结构可能代码略有差异，不过不重要！）。然后取第一个有值的节点的值，但是为了防止右侧节点没有更深层级的子节点，所以所有节点都得加入，这里并不能做剪枝优化。

深度优先 dfs

可以递归来一个从右节点开始的深度优先，然后用一个数值记录下层数，每层放最先找到的那个值即可。这个没写代码，因为两个方法复杂度一致，没啥大意思。

至此，上代码

代码

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func rightSideView(root *TreeNode) []int {
    if root == nil {
        return nil
    }
    res := make([]int, 0)
    nodeList := []*TreeNode{root}
    thisFloorHasPut := false
    for len(nodeList) > 0 {
        // 每层标记位重置
        thisFloorHasPut = false
        // 暂存每层节点，指定容量更节约
        thisFloorNodeList := make([]*TreeNode, 0, len(nodeList)*2)
        for _, node := range nodeList {
            if !thisFloorHasPut {
                res = append(res, node.Val)
                thisFloorHasPut = true
            }
            if node.Right != nil {
                thisFloorNodeList = append(thisFloorNodeList, node.Right)
            }
            if node.Left != nil {
                thisFloorNodeList = append(thisFloorNodeList, node.Left)
            }
        }
        nodeList = thisFloorNodeList
    }
    return res
}