199. 二叉树的右视图

题目#

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

示例:

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

   1            <---
 /   \
2     3         <---
 \     \
  5     4       <---

思路#

层序遍历的变种，只保存每层的最后一个元素即可。

代码#

func rightSideView(root *TreeNode) []int {
    result := []int{}
    if root == nil {
        return result
    }

    queue := []*TreeNode{}
    queue = append(queue, root)
    for len(queue) > 0 {
        var v int
        l := len(queue)
        for i := 0; i < l; i++ {
            n := queue[0]
            queue = queue[1:]

            // 这里没有用数组，而是不断更新 v 的值
            v = n.Val
            if n.Left != nil {
                queue = append(queue, n.Left)
            }
            if n.Right != nil {
                queue = append(queue, n.Right)
            }
        }
        result = append(result, v)
    }

    return result
}