高频算法面试题（三十三）- 输出二叉树的右视图

发表于

「这是我参与11月更文挑战的第 18 天，活动详情查看：2021最后一次更文挑战」

刷算法题，从来不是为了记题，而是练习把实际的问题抽象成具体的数据结构或算法模型，然后利用对应的数据结构或算法模型来进行解题。个人觉得，带着这种思维刷题，不仅能解决面试问题，也能更多的学会在日常工作中思考，如何将实际的场景抽象成相应的算法模型，从而提高代码的质量和性能

输出二叉树的右视图

题目来源：LeetCode-199. 二叉树的右视图

题目描述

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

示例

示例 1

1.png

1
2
csharp复制代码输入: [1,2,3,null,5,null,4]
输出: [1,3,4]

示例 2

1
2
ini复制代码输入: [1,null,3]
输出: [1,3]

示例 3

1
2
ini复制代码输入: []
输出: []

提示：

  • 二叉树的节点个数的范围是 [0,100]
  • 100 <= Node.val <= 100

解题

解法一：深度优先搜索

思路

本题最容易想到的思路就是，如果我能遍历每一层，然后输出每一层的最右边的结点就可以了。我们知道，二叉树的层序遍历，需要借助队列来实现。实现的过程中发现，我们没法记录队列中的结点当前属于哪一层，因此这个方法其实是行不通的

那换一种思路，用深度优先搜索，如果对于树的每一层，我都先访问它的右子树，那么每一层我们访问到的第一个节点，一定是最右边的那个节点（假设右节点是存在的）

深度优先搜索：随意选择一个岔路口来走，走着走着发现走不通的时候，就回退到上一个岔路口，重新选择一条路继续走，直到走完所有的情况

通过上边的方式，我们就可以记录每一层访问的第一个节点，等搜索完所有的层，就得到了我们想要的结果（深度优先搜索，我们通常是用栈来实现）。你可能有个思路，但是并不是很明白，画图是最好的方式，用图来展示整个过程

2.png

有了思路，代码还算比较好写，需要借助两个栈

nodeStack：用来记录每次遍历到的节点（入栈的时候，右子树后进，这样访问栈的时候，每一层第一个出来的，一定是右子树（假设右子树存在）） depthStack：记录树的深度，目的是为了知道，每一层是否已经有我们需要的结点了，如果已经有了，该层的剩余结点就不需要了

代码

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
40
41
go复制代码//输出二叉树的右视图
//深度优先搜索实现
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
}

解法二：广度优先搜索

思路

广度优先搜索：是一种“地毯式”层层推进的搜索策略，即先查找离起始顶点最近的，然后是次近的，依次往外搜索

如果理解了上边的深度优先的解法，用广度优先来解决就很简单了。我首先知道的是，用广度优先搜索，需要借助队列来实现，队列的夜店是先进先出，所以我们在搜索树的时候，可以让左子树先进队列，右子树后进，这样我们在访问每一层的结点的时候，不断更新我们需要的值，每一层最后一个访问到的，一定就是右子树

3.png
思路和上边一样，需要维护两个队列，一个记录结点，一个记录层。如果你看懂了上边的代码，下边这个代码，一看就明白

代码

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
40
41
42
43
44
45
46
ini复制代码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
}

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

0%