leetcode 112 路径总和

作者: Arsenal4ever | 来源:发表于2020-01-27 21:43 被阅读0次

俺的写法是递归找到每一条路径,算出总和添加到一个列表中,在判断存在不存在。

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

class Solution(object):
    def hasPathSum(self, root, sum):
        """
        :type root: TreeNode
        :type sum: int
        :rtype: bool
        """
        if not root:
            return False
        self.path = []
        self.getSum(root, 0)
        return sum in self.path

    def getSum(self, root, temp):
        if not root.left and not root.right:
            t = root.val + temp
            self.path.append(t)
        if root.left:
            t = root.val + temp
            self.getSum(root.left, t)
        if root.right:
            t = root.val + temp
            self.getSum(root.right, t)
        

看了下比较好的写法,直接用给的和递归减去节点值,判断相等不相等。

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

class Solution(object):
    def hasPathSum(self, root, sum):
        """
        :type root: TreeNode
        :type sum: int
        :rtype: bool
        """
        if root is None:
            return False
        if root.left is None and root.right is None:
            return sum == root.val
        else:
            return self.hasPathSum(root.left, sum-root.val) or self.hasPathSum(root.right, sum-root.val)

相关文章

  • 回溯,贪心,动态规划

    1.回溯算法思想leetcode 112 号算法题:路径总和leetcode 113 号算法题:路径总和 IIle...

  • Leetcode 112 路径总和

    112. 路径总和[https://leetcode-cn.com/problems/path-sum/] 题意:...

  • 【D4】路径总和 & 路径总和 II (LC 112&113)

    112. 路径总和[https://leetcode-cn.com/problems/path-sum/] 问题描...

  • Leetcode 112 路径总和

    路径总和 题目 给定一个二叉树和一个目标和,判断该树中是否存在根节点到叶子节点的路径,这条路径上所有节点值相加等于...

  • leetcode 112 路径总和

    俺的写法是递归找到每一条路径,算出总和添加到一个列表中,在判断存在不存在。 看了下比较好的写法,直接用给的和递归减...

  • LeetCode - #112 路径总和

    前言 我们社区陆续会将顾毅(Netflix 增长黑客,《iOS 面试之道》作者,ACE 职业健身教练。)的 Swi...

  • LeetCode 112. 路径总和

    题目 给定一个二叉树和一个目标和,判断该树中是否存在根节点到叶子节点的路径,这条路径上所有节点值相加等于目标和。 ...

  • leetcode--112--路径总和

    题目:给定一个二叉树和一个目标和,判断该树中是否存在根节点到叶子节点的路径,这条路径上所有节点值相加等于目标和。 ...

  • leetcode 112. 路径总和

  • leetcode 112.路径总和

    题目描述 给定一个二叉树和一个目标和,判断该树中是否存在根节点到叶子节点的路径,这条路径上所有节点值相加等于目标和...

网友评论

    本文标题:leetcode 112 路径总和

    本文链接:https://www.haomeiwen.com/subject/ppoethtx.html