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

有个比较好的方案是层序遍历后，找每层最后一个位置

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func rightSideView(root *TreeNode) []int {
	if root == nil {
		return []int{}
	}
	levels := [][]int{}
	  
	stack := []*TreeNode{root}
	  
	for i:=0; len(stack)>0; i++ {
		levels = append(levels, []int{})
		q := []*TreeNode{}
			for j:=0; j<len(stack); j++ {
				nod := stack[j]
				levels[i] = append(levels[i], nod.Val)
				if nod.Left != nil {
					q = append(q, nod.Left)
				}
				if nod.Right != nil {
					q = append(q, nod.Right)
				}
			}
		stack = q
	}
	  
	ans := []int{}
	for _, l := range levels {
		last := l[len(l)-1]
		ans = append(ans, last)
	}
	return ans
}