二叉树中和为某一值的路径
二叉树中和为某一值的路径
FollowMee 发表于5个月前
二叉树中和为某一值的路径
  • 发表于 5个月前
  • 阅读 2
  • 收藏 0
  • 点赞 0
  • 评论 0

二叉树中和为某一值的路径

题目内容:输入一颗二叉树和一个整数,打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径

解法:二叉树深度优先遍历附带记忆栈完成

# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    # 返回二维列表,内部每个列表表示找到的路径
    def FindPath(self, root, expectNumber):
        # write code here
        if not root:
            return []
        pl = []
        path = []
        cs = 0
        self.findPath(root, expectNumber, path, cs, pl)
        return pl
    def findPath(self, root, en, path, cs, pl):
        cs = cs + root.val
        path.append(root.val)
        if(cs == en and (root.left is None and root.right is None)):
            temp=[]                #path是可变对象
            temp.extend(path)
            pl.append(temp)
        if root.left:
            self.findPath(root.left, en, path, cs, pl)
        if root.right:
            self.findPath(root.right, en, path, cs, pl)
        cs = cs - path.pop()

注意:path是可变对象,添加路径时转换为不可变对象

标签: Python 算法
共有 人打赏支持
粉丝 2
博文 8
码字总数 2003
×
FollowMee
如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!
* 金额(元)
¥1 ¥5 ¥10 ¥20 其他金额
打赏人
留言
* 支付类型
微信扫码支付
打赏金额:
已支付成功
打赏金额: