文章目录
- LeetCode 257. 二叉树的所有路径
- 思路
- 递归
- 版本一:非常明确的回溯代码
- 版本二:精简的回溯代码
LeetCode 257. 二叉树的所有路径
LeetCode 257. 二叉树的所有路径
给定一个二叉树,返回所有从根节点到叶子节点的路径。
说明: 叶子节点是指没有子节点的节点。
示例:
输入:
1/ \
2 3\5
输出: ["1->2->5", "1->3"]
解释: 所有根节点到叶子节点的路径为: 1->2->5, 1->3
思路
这道题目要求从根节点到叶子的路径,所以需要前序遍历,这样才方便让父节点指向孩子节点,找到对应的路径。
在这道题目中将第一次涉及到回溯,因为我们要把路径记录下来,需要回溯来回退一个路径再进入另一个路径。
前序遍历以及回溯的过程如图:
回溯和递归中回归的区别:
回溯
:因为我们要把路径记录下来,需要回溯来回退一个路径再进入另一个路径。
回归
:下层函数栈执行完成后,回归到上层函数栈来实际上,回溯和回归都是伴随递归出现的,
只是回溯比回归多了一个路径回退的操作。
我们先使用递归的方式,来做前序遍历。要知道递归和回溯就是一家的,本题也需要回溯。
递归
递归函数参数以及返回值
要传入根节点root
,记录每一条路径的str
,和存放结果集的res
,这里递归不需要返回值,代码如下:
func dfs(root *TreeNode,res *[]string,str string) {}
确定递归终止条件
在写递归的时候都习惯了这么写:
if root == nil {终止处理逻辑
}
但是本题的终止条件这样写会很麻烦,因为本题要找到叶子节点,就开始结束的处理逻辑了(把路径放进res
里)。
那么什么时候算是找到了叶子节点? 是当 root
不为空,其左右孩子都为空的时候,就找到叶子节点。
所以本题的终止条件是:
if root.Left == nil && root.Right == nil {终止处理逻辑}
为什么没有判断root
是否为空呢,因为下面的逻辑可以控制空节点不入循环。
再来看一下终止处理的逻辑。
这里使用string
类型str
来记录路径,注意在下面处理单层递归逻辑的时候,要做回溯,可能有的同学问了,我看有些人的代码也没有回溯啊。
其实是有回溯的,只不过隐藏在函数调用时的参数赋值里(值传递),下文我还会提到。
这里我们使用string
类型的str
来记录路径,那么终止处理逻辑如下:
if root.Left == nil && root.Right == nil {*res = append(*res,str)}
确定单层递归逻辑
因为是前序遍历,需要先处理中间节点,中间节点就是我们要记录路径上的节点,先加到str
中。
str = str + "->" + fmt.Sprintf("%d",root.Left.Val)
然后是递归和回溯的过程,上面说过没有判断root
是否为空,那么在这里递归的时候,如果为空就不进行下一层递归了。
所以递归前要加上判断语句,下面要递归的节点是否为空,如下
if root.Left != nil {dfs(root.Left,res,str)}if root.Right != nil {dfs(root.Right,res,str)}
此时还没完,递归完,要做回溯啊,因为str
不能只一直加入节点,它还要删节点,然后才能加入新的节点。
那么回溯要怎么回溯呢,一些同学会这么写,如下:
if root.Left != nil {dfs(root.Left,res,str)}if root.Right != nil {dfs(root.Right,res,str)}l := len("->" + fmt.Sprintf("%d",root.Left.Val))str = str[0:len(str)-l] // 回溯
这个回溯就有很大的问题,我们知道,回溯和递归是一一对应的,有一个递归,就要有一个回溯
,这么写的话相当于把递归和回溯拆开了, 一个在花括号里,一个在花括号外。
所以回溯要和递归永远在一起
,世界上最遥远的距离是你在花括号里,而我在花括号外!
那么代码应该这么写:
if root.Left != nil {str = str + "->" + fmt.Sprintf("%d",root.Left.Val)dfs(root.Left,res,str)l := len("->" + fmt.Sprintf("%d",root.Left.Val))str = str[0:len(str)-l] // 回溯}if root.Right != nil {str = str + "->" + fmt.Sprintf("%d",root.Right.Val)dfs(root.Right,res,str)l := len("->" + fmt.Sprintf("%d",root.Right.Val))str = str[0:len(str)-l] // 回溯}
那么本题整体Go
代码如下:
版本一:非常明确的回溯代码
/*** Definition for a binary tree node.* type TreeNode struct {* Val int* Left *TreeNode* Right *TreeNode* }*/
func binaryTreePaths(root *TreeNode) []string {if root == nil {return []string{}}res := make([]string,0)str := fmt.Sprintf("%d",root.Val)dfs(root,&res,str)return res
}func dfs(root *TreeNode,res *[]string,str string) {if root.Left == nil && root.Right == nil {*res = append(*res,str)}if root.Left != nil {str = str + "->" + fmt.Sprintf("%d",root.Left.Val)dfs(root.Left,res,str)l := len("->" + fmt.Sprintf("%d",root.Left.Val))str = str[0:len(str)-l] // 回溯}if root.Right != nil {str = str + "->" + fmt.Sprintf("%d",root.Right.Val)dfs(root.Right,res,str)l := len("->" + fmt.Sprintf("%d",root.Right.Val))str = str[0:len(str)-l] // 回溯}
}
如上的Go
代码充分体现了回溯。
那么如上代码可以精简成如下代码:
版本二:精简的回溯代码
/*** Definition for a binary tree node.* type TreeNode struct {* Val int* Left *TreeNode* Right *TreeNode* }*/
func binaryTreePaths(root *TreeNode) []string {if root == nil {return []string{}}res := make([]string,0)str := fmt.Sprintf("%d",root.Val)dfs(root,&res,str)return res
}func dfs(root *TreeNode,res *[]string,str string) {if root.Left == nil && root.Right == nil {*res = append(*res,str)}if root.Left != nil {dfs(root.Left,res,str + "->" + fmt.Sprintf("%d",root.Left.Val))}if root.Right != nil {dfs(root.Right,res,str + "->" + fmt.Sprintf("%d",root.Right.Val))}
}
如上代码精简了不少,也隐藏了不少东西。
注意在函数定义的时候func dfs(root *TreeNode,res *[]string,str string)
,定义的是str string
,每次都是复制赋值,不用使用指针,否则就无法做到回溯的效果。
那么在如上代码中,貌似没有看到回溯的逻辑,其实不然,回溯就隐藏在 dfs(root.Left,res,str + "->" + fmt.Sprintf("%d",root.Left.Val))
中的str + "->" + fmt.Sprintf("%d",root.Left.Val)
。 每次函数调用完,str
依然是没有加上"->" + fmt.Sprintf("%d",root.Left.Val)
的,这就是回溯了。
综合以上,第二种递归的代码虽然精简但把很多重要的点隐藏在了代码细节里,第一种递归写法虽然代码多一些,但是把每一个逻辑处理都完整的展现出来了。