二叉树的所有路径
LeetCode257. 二叉树的所有路径
题目描述
给你一个二叉树的根节点 root ，按 任意顺序 ，返回所有从根节点到叶子节点的路径。
叶子节点 是指没有子节点的节点。
思路
这道题目要求从根节点到叶子的路径，所以需要前序遍历(中左右)，并且我们要把路径记录下来，需要用回溯来回退
- 递归函数参数和返回值
- 参数：传入根节点、记录每一条路径的
path、存放结果集的result
- 返回值：不需要
- 确定递归终止条件
- 终止条件：找到叶子节点
- 找到叶子节点：传入的根节点不为空，且其左右孩子都为空
- 确定单层递归逻辑
- 因为是前序遍历，需要先处理中间节点，中间节点就是我们要记录路径上的节点，先放进
path中
- 然后是递归和回溯的过程
- 回溯：因为
path不能一直加入节点，它还要删节点，然后才能加入新的节点。回溯和递归是一一对应的，有一个递归，就要有一个回溯
代码
Go
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
|
func binaryTreePaths(root *TreeNode) []string {
//动态创建切片 切片中的成员类型为string 当前切片具备的长度为0
result := make([]string, 0) //结果集
//定义函数类型变量travel
var travel func(node *TreeNode, s string)
//实现匿名函数并赋值给函数类型的变量travel用于递归调用
travel = func(node *TreeNode, s string) {
//传入的根节点其左右孩子都为空 遇到叶子节点
if node.Left == nil && node.Right == nil {
//拼接节点值到字符串中
v := s + strconv.Itoa(node.Val)
//向切片添加元素 返回新的切片result
result = append(result, v)
return
}
//非叶子节点 将该节点值拼接到字符串s后面 (中)
s = s + strconv.Itoa(node.Val) + "->"
//左
if node.Left != nil {
travel(node.Left, s) //递归
}
//右
if node.Right != nil {
travel(node.Right, s)
}
}
//使用函数类型变量travel调用刚才实现的匿名函数
travel(root, "")
return result
}
|
Link
GitHub