LeetCode-112-路径总和

原题链接：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)