199. 二叉树的右视图

题目描述：

给定一个二叉树的 根节点 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

---

解题分析及思路：

方法：广度优先搜索

这道题考察的是二叉树的遍历，不熟悉二叉树的遍历可以查看二叉树。

思路：

由于是获取到每一层的最右边的节点，所以可以使用广度优先搜索的方法来解决。

• 从根节点开始，每一层都从左到右遍历，只保留每一层最右边的节点。
• 用一个队列来存储每一层的节点，每次遍历完一层时，将每一个值都更新到结果中，最后就是最右边的节点的值就会存放在结果集中，而前置节点的值都会被覆盖掉。
• 重复上述步骤，直到队列为空。

func rightSideView(root *TreeNode) (ans []int) {
	if root == nil {
		return
	}
	var queue = make([]*TreeNode, 0)
	var index = 0
	queue = append(queue, root)
	for len(queue) != 0 {
		var queue1 = make([]*TreeNode, 0)
		ans = append(ans, queue[0].Val)
		for i := range queue {
			ans[index] = queue[i].Val
			if queue[i].Left != nil {
				queue1 = append(queue1, queue[i].Left)
			}
			if queue[i].Right != nil {
				queue1 = append(queue1, queue[i].Right)
			}
		}
		index++
		queue = queue1
	}
	return
}

复杂度：

• 时间复杂度：O(N)，其中 N 是树中的节点个数.
• 空间复杂度：O(1)，只使用常数额外空间。

执行结果：

• 执行耗时:0 ms,击败了100.00% 的Go用户
• 内存消耗:2.1 MB,击败了55.24% 的Go用户