剑指Offer34-二叉树中和为某一值的路径

兴趣爱好交流 每日一题
1

剑指Offer34-二叉树中和为某一值的路径

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

示例:

给定如下二叉树，以及目标和 target = 22，


              5

             / \

            4   8

           /   / \

          11  13  4

         /  \    / \

        7    2  5   1

返回:


[

   [5,4,11,2],

   [5,8,4,5]

]

提示：


节点总数 <= 10000

来源：力扣（LeetCode）

链接：力扣

一解

使用递归进行先序遍历：

  • way：记录先序遍历路径

  • 如果 way 的“和”达到 target 值，并且是叶子节点，就加入到 res 中


# Definition for a binary tree node.

# class TreeNode:

#     def __init__(self, val=0, left=None, right=None):

#         self.val = val

#         self.left = left

#         self.right = right

class Solution:

    def pathSum(self, root: TreeNode, target: int) -> List[List[int]]:

        if not root: return []

        res = []

        def tmp(root, way):

            if sum(way) == target and not root.left and not root.right:

                import copy

                res.append(copy.deepcopy(way))

            if root.left: tmp(root.left, way + [root.left.val])

            if root.right: tmp(root.right, way + [root.right.val])

        tmp(root, [root.val])

        return res

二解

与一解思路相同，区别如下：

  • 递归传递的不是数组，而是目标值（tar）

  • 省去了 sum(way) 操作

  • 使用 list(path) 替代深拷贝函数


# Definition for a binary tree node.

# class TreeNode:

#     def __init__(self, val=0, left=None, right=None):

#         self.val = val

#         self.left = left

#         self.right = right

class Solution:

    def pathSum(self, root: TreeNode, target: int) -> List[List[int]]:

        res, path = [], []

        def tmp(root, tar):

            if not root: return

            tar -= root.val

            path.append(root.val)

            if tar == 0 and not root.left and not root.right:

                res.append(list(path))

            tmp(root.left, tar)

            tmp(root.right, tar)

            path.pop()

        tmp(root, target)

        return res