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

怎样求python二叉树路径和

发表于：2025-02-04 作者：千家信息网编辑

千家信息网最后更新 2025年02月04日，这篇文章给大家介绍怎样求python二叉树路径和，内容非常详细，感兴趣的小伙伴们可以参考借鉴，希望对大家能有所帮助。给定一个二叉树和一个目标和，判断该树中是否存在根节点到叶子节点的路径，这条路径上所有

千家信息网最后更新 2025年02月04日怎样求python二叉树路径和

这篇文章给大家介绍怎样求python二叉树路径和，内容非常详细，感兴趣的小伙伴们可以参考借鉴，希望对大家能有所帮助。

给定一个二叉树和一个目标和，判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和。

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

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

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

返回 true, 因为存在目标和为 22 的根节点到叶子节点的路径 5->4->11->2。

解题思路：

1，对于二叉树类型题目一般都是递归解

2，递归有两种：自根向下和自叶子向上

3，对于相等类型题目和最大值题目解题思路相反，本题采用自根向下

/** * Definition for a binary tree node. * type TreeNode struct { *     Val int *     Left *TreeNode *     Right *TreeNode * } */func hasPathSum(root *TreeNode, sum int) bool {    if root==nil{        return false    }    if root.Left==nil && root.Right==nil{        return root.Val==sum    }    return hasPathSum(root.Left,sum-root.Val)||hasPathSum(root.Right,sum-root.Val)}

给定一个二叉树和一个目标和，找到所有从根节点到叶子节点路径总和等于给定目标和的路径。

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

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

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

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

思路：

1，同样是递归，需要每一次把走过的路径存下来传下去，如果满足条件就返回，否则舍弃

2，注意golang 传slice 和map的坑，虽然slice的len是每次传值，但是数据地址是一样的，所以会覆盖掉，每次数据结果都不一样

3，解决办法copy函数进行复制。

/** * Definition for a binary tree node. * type TreeNode struct { *     Val int *     Left *TreeNode *     Right *TreeNode * } */func pathSum(root *TreeNode, sum int) [][]int {    var r [][]int    if root ==nil{        return r    }    var temp []int    return walk(root,sum,temp)}
func walk(root *TreeNode, sum int,temp1 []int)([][]int){     var r [][]int    if root==nil{        return r    }    temp:=make([]int,len(temp1))    copy(temp,temp1)     temp=append(temp,root.Val)   //fmt.Println(root,temp,sum)     if root.Left==nil && root.Right==nil{        if root.Val==sum{            r=append(r,temp)        // fmt.Println(root,temp,sum,r)            return r        }         return r     }                    tl:=walk(root.Left,sum-root.Val,temp)        tr:=walk(root.Right,sum-root.Val,temp)
         if len(tl)>0 {             r=append(r,tl...)         }         if len(tr)>0 {             r=append(r,tr...)         }    return r}