本文主要是介绍Python算法练习 10.16，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
leetcode 437 路径总和III
给定一个二叉树的根节点 root ，和一个整数 targetSum ，求该二叉树里节点值之和等于 targetSum 的 路径 的数目。
路径 不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。
示例 1：
输入：root = [10,5,-3,3,2,null,11,3,-2,null,1], targetSum = 8 输出：3 解释：和等于 8 的路径有 3 条，如图所示。示例 2：
输入：root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22 输出：3
自己写的...没通过
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution(object):def pathSum(self, root, targetSum):""":type root: TreeNode:type targetSum: int:rtype: int"""def singlePathSum(pathValList,count, targetSum, answerList):i = 1 # 步长while i <= len(pathValList):j = 0while j + i <= len(pathValList):k = jsum = 0tmpArr = []while k < j + i:sum += pathValList[k]tmpArr.append(pathValList[k])k += 1if sum == targetSum:count += 1print(tmpArr)answerList.append(tmpArr)j += 1i += 1return countdef goNextlevel(root, pathValList, count, targetSum, answerList):print("curVal=", root.val)pathValList.append(root.val)if not root.left and not root.right:count = singlePathSum(pathValList,count, targetSum, answerList)return countif root.left:count = goNextlevel(root.left, pathValList, count, targetSum, answerList)pathValList.pop()if root.right:count = goNextlevel(root.right, pathValList, count, targetSum, answerList)pathValList.pop()return countcount = 0if not root:return countelse:if not root.left and not root.right:if root.val == targetSum:count += 1return countpathValList = []answerList = []pathValList.append(root.val)if root.left:count = goNextlevel(root.left, pathValList, count, targetSum, answerList)if root.right:count = goNextlevel(root.right, pathValList, count, targetSum, answerList)answerList = [x for i, x in enumerate(answerList) if x not in answerList[:i]]return len(answerList)
题解：每向下一层就把targetSum的值减掉当前节点的值
其实就是把每个节点作为根节点，分治法再计算每个子树的符合条件的路径个数，求和
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution(object):def pathSum(self, root, targetSum):def rootSum(root, targetSum):if root is None:return 0ret = 0if root.val == targetSum:ret += 1ret += rootSum(root.left, targetSum - root.val)ret += rootSum(root.right, targetSum - root.val)return retif root is None:return 0ret = rootSum(root, targetSum)ret += self.pathSum(root.left, targetSum)ret += self.pathSum(root.right, targetSum)return ret这篇关于Python算法练习 10.16的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
