【leetcode】112. 路径总和

题目

112. 路径总和

给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和 targetSum 。如果存在，返回 true ；否则，返回 false 。

叶子节点 是指没有子节点的节点。

题解

1. 迭代

1. 判断叶子节点
2. 将【root，root.val】数组保存，即每个叶子节点保存父节点到叶子节点的和

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):def hasPathSum(self, root, targetSum):""":type root: Optional[TreeNode]:type targetSum: int:rtype: bool"""if not root:return Falsestack = []stack.append([root, root.val])while stack:node, cur_sum = stack.pop()if not node.left and not node.right:if cur_sum == targetSum:return True if node.right:stack.append([node.right, cur_sum + node.right.val])if node.left:stack.append([node.left, cur_sum + node.left.val])return False

2. 递归

1. 判断空节点
2. 判断叶子节点及其是否等于目标值
3. 进行递归，targetSum = targetSum - root.val

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):def hasPathSum(self, root, targetSum):""":type root: Optional[TreeNode]:type targetSum: int:rtype: bool"""if not root:return Falseif not root.left and not root.right and root.val == targetSum:return True return self.hasPathSum(root.left, targetSum - root.val) or self.hasPathSum(root.right, targetSum - root.val)