LeetCode-112-路径总和

2020-11-14  本文已影响0人  阿凯被注册了

原题链接:https://leetcode-cn.com/problems/path-sum/

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


image.png

解题思路:

  1. 迭代:维护两个队列,一个存储遍历过的节点,另一个存储至该节点时的val和,当该节点是叶子节点时(没有左右叶子节点),判断val和与sum,相等则返回True;
  2. 递归: 将从根节点到叶子节点val和的问题转换为,每一个节点的val和是否等于sum-已经遍历过的节点val和的问题;

Python3代码:

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

class Solution:
    def hasPathSum(self, root: TreeNode, sum: int) -> bool:
        # 迭代
        if not root:
            return False
        node_queue = [root]
        val_queue = [root.val]

        while node_queue:
            node = node_queue.pop(0)
            val = val_queue.pop(0)

            # node不存在左右叶子节点,即node是叶子节点,此时判断
            if not node.left and not node.right: 
                if val == sum:
                    return True
                continue
            # node存在左叶子节点
            if node.left:
                node_queue.append(node.left)
                val_queue.append(val+node.left.val)
            # node存在右叶子节点
            if node.right:
                node_queue.append(node.right)
                val_queue.append(val+node.right.val)
        return False
class Solution:
    def hasPathSum(self, root: TreeNode, sum: int) -> bool:
        if not root:
            return False
        if not root.left and not root.right:
            return root.val == sum
        return self.hasPathSum(root.left, sum-root.val) or self.hasPathSum(root.right, sum-root.val)
上一篇 下一篇

猜你喜欢

热点阅读