欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

剑指Offer 34. 二叉树中和为某一值的路径(Medium)

程序员文章站 2024-01-02 11:55:52
【题目链接】题解二叉树中和为某一值的路径(回溯法,清晰图解)思路代码# Definition for a binary tree node.# class TreeNode:# def __init__(self, x):# self.val = x# self.left = None# self.right = Noneclass Solution: ### 1209 先序遍历 + 路径记录(48 ms,1....

剑指Offer 34. 二叉树中和为某一值的路径(Medium)
【题目链接】

题解

  1. 二叉树中和为某一值的路径(回溯法,清晰图解)

思路

剑指Offer 34. 二叉树中和为某一值的路径(Medium)
剑指Offer 34. 二叉树中和为某一值的路径(Medium)
剑指Offer 34. 二叉树中和为某一值的路径(Medium)

代码

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    ### 1209 先序遍历 + 路径记录(48 ms,15.2 MB)
    def pathSum(self, root: TreeNode, sum: int) -> List[List[int]]:
        def recur(root, target):
            # 若节点为空,则直接返回
            if not root: return
            
            path.append(root.val) # 每遍历到一个节点,则将其加入当前path
            target -= root.val    # 当前目标值减掉当前的节点值

            # 若恰好达到目标值 且 此节点为叶节点(即左、右子节点均不存在),表示寻找到一条符合条件的路径,加入待返回列表res
            if target == 0 and not root.left and not root.right: res.append(list(path)) # 注意:使用list来对当前path实例化,若直接传入path,则相当于浅拷贝!

            # 1.若上面的if语句执行,则下面递归左、右子树均会直接返回(因为叶节点不含有子树)
            # 2.若上面的if语句未执行,则继续递归左、右子树,寻找可能的路径
            recur(root.left, target)
            recur(root.right, target)

            path.pop()     # 在当前path中去掉当前节点,表示回溯

        res, path = [], []
        recur(root, sum)   # 开始时传入根节点root和初始目标值sum

        return res

本文地址:https://blog.csdn.net/newCraftsman/article/details/110928715

上一篇:

下一篇: