LeetCode 437. Path Sum III

Description

You are given a binary tree in which each node contains an integer value.

Find the number of paths that sum to a given value.

The path does not need to start or end at the root or a leaf, but it must go downwards (traveling only from parent nodes to child nodes).

The tree has no more than 1,000 nodes and the values are in the range -1,000,000 to 1,000,000.

Example:

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

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

Return 3. The paths that sum to 8 are:

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

思路

  • 二叉树相关的题目很多情况下都需要用到递归来解决。
  • 根据题意,求使得和为给定数字的种树。不一定要求从根节点开始。
  • 思考递归这种解题方式时,需要将原问题拆解成更小的子问题,并且假设子问题已经解决。
  • 二叉树有左子树和右子树,我们假设左右子树的问题已经解决,即已经知道了左右子树可以形成满足条件的种数;那么此时还剩下以当前节点为起始节点可以形成的种数。
  • 即整颗二叉树可以形成的路径等于给定值的总数 = 必须以 node 节点为开始节点的种数 + node 左子树可以形成的路径数 + node 右子树可以形成的路径树。
  • 在求解以 node 节点开始的路径和为给定值的种数时候,可以使用 前/中/后 三种遍历方式中的任意一种。
  • 这里采用中序遍历的一种方式。

# -*- coding: utf-8 -*-
# @Author:             何睿
# @Create Date:        2020-05-01 17:30:03
# @Last Modified by:   何睿
# @Last Modified time: 2020-05-01 19:54:16

# Definition for a binary tree node.


class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None


class Solution:
    def pathSum(self, root: TreeNode, sum: int) -> int:
        if not root:
            return 0

        return self.sumRoot(root, 0, sum) + self.pathSum(root.left, sum) + self.pathSum(root.right, sum)

    def sumRoot(self, root, pre, sum_):

        if not root:
            return 0
        pre += root.val

        left = self.sumRoot(root.left, pre, sum_)
        right = self.sumRoot(root.right, pre, sum_)

        return (pre == sum_) + left + right

源代码文件在 这里 。


©本文是原创文章,欢迎转载,转载需保留 文章来源 ,作者信息和本声明.

Posted in LeetCode and tagged , .

花若盛開,蝴蝶自來. 分享学习,每天进步一点点

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.