高频算法面试题（四十四）- 二叉树的所有路径

发表于

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

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

二叉搜索树与双向链表

题目来源：LeetCode-257. 二叉树的所有路径

题目描述

给你一个二叉树的根节点 root ，按 任意顺序 ，返回所有从根节点到叶子节点的路径。

叶子节点 是指没有子节点的节点

示例 1：

1.png

1
2
css复制代码输入：root = [1,2,3,null,5]
输出：["1->2->5","1->3"]

示例 2：

1
2
css复制代码输入：root = [1]
输出：["1"]

提示：

  • 树中节点的数目在范围 [1, 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
go复制代码//二叉树的所有路径
//深度优先搜索
var treePath []string
func binaryTreePaths(root *TreeNode) []string {
	treePath = []string{}
	dfsEachPath(root, "")
	return treePath
}

func dfsEachPath(root *TreeNode, path string) {
	if root != nil {
		eachPath := path
		eachPath += strconv.Itoa(root.Val)
		if root.Left == nil && root.Right == nil {
			treePath = append(treePath, eachPath)
		} else {
			eachPath += "->"
			dfsEachPath(root.Left, eachPath)
			dfsEachPath(root.Right, eachPath)
		}
	}
}

解法二：广度优先搜索

思路

前边已经做了很多二叉树的题，很多都用深度和广度优先搜索进行解题，基本上用深度优先搜索能解的，都可以尝试用广度优先搜索来解

广度优先搜索首先我们知道需要借助队列，本题我们需要维护两个队列，分别用来记录每一层的节点和根节点到当前节点的路径

如果遍历的当前节点是叶子结点，则说明当前这条路径可以放到结果集中了；如果是非叶子结点，则将它的子节点放入到节点队列中

代码

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
go复制代码//广度优先搜索实现
func binaryTreePaths2(root *TreeNode) []string {
	paths := []string{}
	if root == nil {
		return paths
	}
	nodeQueue := []*TreeNode{root}
	pathQueue := []string{strconv.Itoa(root.Val)}
	for i :=0; i < len(nodeQueue); i++ {
		node, path := nodeQueue[i], pathQueue[i]
		if node.Left == nil && node.Right == nil {
			paths = append(paths, path)
			continue
		}
		if node.Left != nil {
			nodeQueue = append(nodeQueue, node.Left)
			pathQueue = append(pathQueue, path+"->"+strconv.Itoa(node.Left.Val))
		}
		if node.Right != nil {
			nodeQueue = append(nodeQueue, node.Right)
			pathQueue = append(pathQueue, path+"->"+strconv.Itoa(node.Right.Val))
		}
	}

	return paths
}

本文转载自: 掘金

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

0%