二叉树的所有路径：回溯算法详解

二叉树的所有路径：回溯算法详解

引用

CSDN

1.

https://blog.csdn.net/YouMing_Li/article/details/142445559

本文详细讲解了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) {}

1. 确定递归终止条件

在写递归的时候都习惯了这么写：

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

1. 确定单层递归逻辑

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

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