导航：首页 > 互联网科技 >

如何分析python二叉树中和为某一值的路径

发表于：2024-11-13 作者：千家信息网编辑

千家信息网最后更新 2024年11月13日，这篇文章给大家介绍如何分析python二叉树中和为某一值的路径，内容非常详细，感兴趣的小伙伴们可以参考借鉴，希望对大家能有所帮助。输入一棵二叉树和一个整数，打印出二叉树中节点值的和为输入整数的所有路径

千家信息网最后更新 2024年11月13日如何分析python二叉树中和为某一值的路径

这篇文章给大家介绍如何分析python二叉树中和为某一值的路径，内容非常详细，感兴趣的小伙伴们可以参考借鉴，希望对大家能有所帮助。

输入一棵二叉树和一个整数，打印出二叉树中节点值的和为输入整数的所有路径。从树的根节点开始往下一直到叶节点所经过的节点形成一条路径。

示例:
给定如下二叉树，以及目标和 sum = 22，

5
             / \
            4   8
           /   / \
          11  13  4
         /  \    / \
        7    2  5   1

[
   [5,4,11,2],
   [5,8,4,5]
]

提示：

节点总数 <= 10000

注意：本题与主站 113 题相同：https://leetcode-cn.com/problems/path-sum-ii/

解题思路：

1，此题只是，先序遍历的一个变形

2，递归执行，深度优先遍历，这个时候sum变为sum－root.Val

3，到达叶子节点的时候，判断sum==root.Val，是则将整个链路加入结果里，否则，继续遍历

4，需要注意一点了，go的slice传递的是值，但是数据引用的是同一份

5，copy的时候需要先make分配空间，否则copy不成功

代码实现

/** * Definition for a binary tree node. * type TreeNode struct { *     Val int *     Left *TreeNode *     Right *TreeNode * } */func pathSum(root *TreeNode, sum int) [][]int {   var p[]int   var r [][]int
   r=dfs(root,sum,p,r)   return r}
func dfs(root *TreeNode, sum int,path []int,ret [][]int)[][]int{    if root==nil {       return ret    }    path=append(path,root.Val)    if root.Left==nil && root.Right==nil {         if sum==root.Val{              p:=make([]int,len(path))             copy(p,path)         ret=append(ret,p)        fmt.Println(1,":",path,p,sum,root,ret)         }        return ret    }    if root.Left==nil{        return dfs(root.Right,sum-root.Val,path,ret)    }
    if root.Right==nil{        return dfs(root.Left,sum-root.Val,path,ret)    }    l:=dfs(root.Left,sum-root.Val,path,ret)    r:=dfs(root.Right,sum-root.Val,path,ret)    fmt.Println(ret,l,r)    ret=append(ret,l...)    ret=append(ret,r...)    return ret}