题目
给定一棵二叉树，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。
示例:
输入: [1,2,3,null,5,null,4]
输出: [1, 3, 4]
解释:
1 <---
/ \
2 3 <---
\ \
5 4 <---
思路
1. dfs 深度优先
因为要求的是右视图, 所以和二叉树的先序遍历相反就可以了, 根节点 --> 右节点 --> 左节点, 把每一层的第一个访问到的节点加入到返回数组中
2. bfs 广度优先
利用广度优先对每层进行便利, 记录下每层的最有一个元素即可
两种时间复杂度都是O(n)
code
go
dfs
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
var res []int
func rightSideView(root *TreeNode) []int {
res = []int{}
dfs(root, 1)
return res
}
func dfs(root *TreeNode, level int) {
if root == nil {
return
}
if level > len(res) {
res = append(res, root.Val)
}
dfs(root.Right, level+1)
dfs(root.Left, level+1)
}
bfs
func rightSideView(root *TreeNode) []int {
var res []int
if root == nil{
return res
}
var queue = []*TreeNode{root}
var level int
for 0 < len(queue) {
length := len(queue)
for 0 < length {
length--
if len(res) == level {
res = append(res, queue[0].Val)
}
if queue[0].Right != nil {
queue = append(queue, queue[0].Right)
}
if queue[0].Left != nil {
queue = append(queue, queue[0].Left)
}
queue = queue[1:]
}
level++
}
return res
}
