高频算法面试题（三十三）- 输出二叉树的右视图
题目描述
给定一个二叉树的 根节点 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
解题
解法一：深度优先搜索
思路
本题最容易想到的思路就是，如果我能遍历每一层，然后输出每一层的最右边的结点就可以了。我们知道，二叉树的层序遍历，需要借助队列来实现。实现的过程中发现，我们没法记录队列中的结点当前属于哪一层，因此这个方法其实是行不通的
那换一种思路，用深度优先搜索，如果对于树的每一层，我都先访问它的右子树，那么每一层我们访问到的第一个节点，一定是最右边的那个节点（假设右节点是存在的）
深度优先搜索：随意选择一个岔路口来走，走着走着发现走不通的时候，就回退到上一个岔路口，重新选择一条路继续走，直到走完所有的情况
通过上边的方式，我们就可以记录每一层访问的第一个节点，等搜索完所有的层，就得到了我们想要的结果（深度优先搜索，我们通常是用栈来实现）。你可能有个思路，但是并不是很明白，画图是最好的方式，用图来展示整个过程
有了思路，代码还算比较好写，需要借助两个栈
nodeStack：用来记录每次遍历到的节点（入栈的时候，右子树后进，这样访问栈的时候，每一层第一个出来的，一定是右子树（假设右子树存在）） depthStack：记录树的深度，目的是为了知道，每一层是否已经有我们需要的结点了，如果已经有了，该层的剩余结点就不需要了
代码
//输出二叉树的右视图
//深度优先搜索实现
func rightSideView(root *TreeNode) []int {
rightViewMap := map[int]int{} //记录每一层第一个访问到的节点值（用map是为了知道每一层是否已经有访问过的结点）
rightView := []int{} //最终存右视图结果的
nodeStack := []*TreeNode{}
depthStack := []int{}
maxDepth := -1 //记录最大深度是为了最后变量右视图
nodeStack = append(nodeStack, root) //根节点入栈
depthStack = append(depthStack, 0) //跟结点属于第0层
for len(nodeStack) != 0 {
node := nodeStack[len(nodeStack)-1] //取出栈顶元素
nodeStack = nodeStack[:len(nodeStack)-1]
currDepth := depthStack[len(depthStack)-1] //当前节点属于哪一层
depthStack = depthStack[:len(depthStack)-1]
if node != nil {
//维护二叉树的最大深度
if currDepth > maxDepth {
maxDepth = currDepth
}
//判断当前层，是否已经有节点被记录了.如果没有，才记录下来
if _, ok := rightViewMap[currDepth];!ok {
rightViewMap[currDepth] = node.Val
}
nodeStack = append(nodeStack, node.Left)
nodeStack = append(nodeStack, node.Right)//右节点后入栈（后进先出）
depthStack = append(depthStack, currDepth+1) //新进入的这两个结点的层数是相同的
depthStack = append(depthStack, currDepth+1)
}
}
for i:=0; i <= maxDepth; i++ {
rightView = append(rightView, rightViewMap[i])
}
return rightView
}复制代码解法二：广度优先搜索
思路
广度优先搜索：是一种“地毯式”层层推进的搜索策略，即先查找离起始顶点最近的，然后是次近的，依次往外搜索
如果理解了上边的深度优先的解法，用广度优先来解决就很简单了。我首先知道的是，用广度优先搜索，需要借助队列来实现，队列的夜店是先进先出，所以我们在搜索树的时候，可以让左子树先进队列，右子树后进，这样我们在访问每一层的结点的时候，不断更新我们需要的值，每一层最后一个访问到的，一定就是右子树
思路和上边一样，需要维护两个队列，一个记录结点，一个记录层。如果你看懂了上边的代码，下边这个代码，一看就明白
代码
func rightSideView2(root *TreeNode) []int {
if root == nil {
return []int{}
}
rightViewMap := map[int]int{}
rightView := []int{}
maxDepth := 0
nodeQueue := []*TreeNode{root}
depthQueue := []int{}
depthQueue = append(depthQueue, 0)
for len(nodeQueue) != 0 {
node := nodeQueue[0]
if len(nodeQueue) <= 1 {
nodeQueue = []*TreeNode{}
} else {
nodeQueue = nodeQueue[1:]
}
currDepth := depthQueue[0]
if len(depthQueue) <= 1 {
depthQueue = []int{}
} else {
depthQueue = depthQueue[1:]
}
if node != nil {
if currDepth > maxDepth {
maxDepth = currDepth
}
rightViewMap[currDepth] = node.Val
nodeQueue = append(nodeQueue, node.Left)
nodeQueue = append(nodeQueue, node.Right)
depthQueue = append(depthQueue, currDepth+1)
depthQueue = append(depthQueue, currDepth+1)
}
}
for i := 0; i <= maxDepth; i++ {
rightView = append(rightView, rightViewMap[i])
}
return rightView
}
作者：书旅
链接：https://juejin.cn/post/7031729980413313032