Go语言树的路径查找实战指南（从零开始掌握二叉树路径搜索算法）

定义二叉树结构

首先，我们需要在 Go 中定义一个二叉树节点结构：

type TreeNode struct {    Val   int    Left  *TreeNode    Right *TreeNode}

这个结构体包含三个字段：节点值 Val，以及指向左右子节点的指针。

查找所有从根到叶子的路径

我们的第一个任务是找出所有从根节点到叶子节点的路径，并以字符串形式返回（如 "1->2->3"）。这可以通过递归轻松实现。

func binaryTreePaths(root *TreeNode) []string {    if root == nil {        return []string{}    }    var result []string    var path []int    var dfs func(*TreeNode)    dfs = func(node *TreeNode) {        if node == nil {            return        }        path = append(path, node.Val)        // 如果是叶子节点，保存当前路径        if node.Left == nil && node.Right == nil {            pathStr := strings.Builder{}            for i, v := range path {                if i > 0 {                    pathStr.WriteString("->")                }                pathStr.WriteString(strconv.Itoa(v))            }            result = append(result, pathStr.String())        } else {            dfs(node.Left)            dfs(node.Right)        }        // 回溯：移除当前节点        path = path[:len(path)-1]    }    dfs(root)    return result}

这段代码使用了深度优先搜索（DFS）配合回溯法。每当到达叶子节点时，就将当前路径加入结果列表；递归返回前，要“回溯”——即从当前路径中移除当前节点，以便探索其他分支。

查找是否存在某条特定路径（路径和等于目标值）

另一个常见问题是：是否存在一条从根到叶子的路径，使得路径上所有节点值之和等于给定的目标值？这也是经典的递归查找树路径问题。

func hasPathSum(root *TreeNode, targetSum int) bool {    if root == nil {        return false    }    // 到达叶子节点    if root.Left == nil && root.Right == nil {        return root.Val == targetSum    }    // 递归检查左右子树    leftOk := hasPathSum(root.Left, targetSum - root.Val)    rightOk := hasPathSum(root.Right, targetSum - root.Val)    return leftOk || rightOk}

这个函数的核心思想是：每向下走一层，就把当前节点的值从目标和中减去。如果最终在叶子节点处剩余和为0，说明找到了符合条件的路径。

完整示例与测试

下面是一个完整的可运行示例，包含主函数和测试用例：

package mainimport (    "fmt"    "strconv"    "strings")type TreeNode struct {    Val   int    Left  *TreeNode    Right *TreeNode}func binaryTreePaths(root *TreeNode) []string {    // ...（此处省略前面定义的函数）}func hasPathSum(root *TreeNode, targetSum int) bool {    // ...（此处省略前面定义的函数）}func main() {    // 构建测试树：    //       1    //      / \    //     2   3    //      \    //       5    root := &TreeNode{Val: 1}    root.Left = &TreeNode{Val: 2}    root.Right = &TreeNode{Val: 3}    root.Left.Right = &TreeNode{Val: 5}    paths := binaryTreePaths(root)    fmt.Println("所有路径:", paths) // 输出: [1->2->5 1->3]    fmt.Println("是否存在路径和为8:", hasPathSum(root, 8)) // true (1+2+5=8)    fmt.Println("是否存在路径和为7:", hasPathSum(root, 7)) // false}

总结

通过本教程，你已经掌握了在 Go 语言中实现Go数据结构教程中最常用的树路径查找方法。无论是列出所有路径，还是判断是否存在满足条件的路径，核心都在于递归与回溯思想的灵活运用。

记住：树的问题大多可以用递归来优雅解决。多练习几遍，你就能熟练应对各种Go语言树路径查找相关的面试题和实际开发需求！

提示：实际项目中建议使用标准库 strconv 和 strings 来处理数字转字符串和拼接，避免性能问题。