LeetCode 257. 二叉树的所有路径（回溯详解）

LeetCode 257. 二叉树的所有路径

LeetCode 257. 二叉树的所有路径

给定一个二叉树，返回所有从根节点到叶子节点的路径。

说明: 叶子节点是指没有子节点的节点。

示例:

输入:

   1/   \
2     3\5

输出: ["1->2->5", "1->3"]

解释: 所有根节点到叶子节点的路径为: 1->2->5, 1->3

思路

这道题目要求从根节点到叶子的路径，所以需要前序遍历，这样才方便让父节点指向孩子节点，找到对应的路径。

在这道题目中将第一次涉及到回溯，因为我们要把路径记录下来，需要回溯来回退一个路径再进入另一个路径。

前序遍历以及回溯的过程如图：

回溯和递归中回归的区别：
回溯：因为我们要把路径记录下来，需要回溯来回退一个路径再进入另一个路径。
回归：下层函数栈执行完成后，回归到上层函数栈来

实际上，回溯和回归都是伴随递归出现的，只是回溯比回归多了一个路径回退的操作。

我们先使用递归的方式，来做前序遍历。要知道递归和回溯就是一家的，本题也需要回溯。

递归

1. 递归函数参数以及返回值
   要传入根节点root，记录每一条路径的str，和存放结果集的res，这里递归不需要返回值，代码如下：

func dfs(root *TreeNode,res *[]string,str string) {}

2. 确定递归终止条件
   在写递归的时候都习惯了这么写：

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)}

3. 确定单层递归逻辑
   因为是前序遍历，需要先处理中间节点，中间节点就是我们要记录路径上的节点，先加到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) 的，这就是回溯了。

综合以上，第二种递归的代码虽然精简但把很多重要的点隐藏在了代码细节里，第一种递归写法虽然代码多一些，但是把每一个逻辑处理都完整的展现出来了。