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

如何解析python二叉树中的路径总和

发表于：2025-01-26 作者：千家信息网编辑

千家信息网最后更新 2025年01月26日，如何解析python二叉树中的路径总和，相信很多没有经验的人对此束手无策，为此本文总结了问题出现的原因和解决方法，通过这篇文章希望你能解决这个问题。给定一个二叉树，它的每个结点都存放着一个整数值。找出

千家信息网最后更新 2025年01月26日如何解析python二叉树中的路径总和

如何解析python二叉树中的路径总和，相信很多没有经验的人对此束手无策，为此本文总结了问题出现的原因和解决方法，通过这篇文章希望你能解决这个问题。

给定一个二叉树，它的每个结点都存放着一个整数值。

找出路径和等于给定数值的路径总数。

路径不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。

二叉树不超过1000个节点，且节点数值范围是 [-1000000,1000000] 的整数。

示例：

root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 8

      10
     /  \
    5   -3
   / \    \
  3   2   11
 / \   \
3  -2   1

返回 3。和等于 8 的路径有:

1.  5 -> 3
2.  5 -> 2 -> 1
3.  -3 -> 11

解题思路：

1，此问题可以拆分成子问题：从根节点开始路径和等于某数的路径个数

2，将所有节点为根的个数和起来

3，以某节点为根的路径和包括多种情况

A，包括和为0的子路径

B，不包括

/** * Definition for a binary tree node. * type TreeNode struct { *     Val int *     Left *TreeNode *     Right *TreeNode * } */func pathSum(root *TreeNode, sum int) int {    count:=sumRoot(root,sum)    if root!=nil{        count+=pathSum(root.Left,sum)        count+=pathSum(root.Right,sum)    }    return count}
func sumRoot(root*TreeNode,sum int)int{    if root==nil{        return 0    }    if root.Val==sum{        return 1 +sumRoot(root.Left,sum-root.Val)+sumRoot(root.Right,sum-root.Val)    }    return sumRoot(root.Left,sum-root.Val)+sumRoot(root.Right,sum-root.Val)}