如何解决leetcode树之路径总和问题

1、问题描述

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

2、解决方案

解决LeetCode树路径总和问题的方法有多种，其中最常用的是递归法和迭代法。

2.1、递归法

递归法是指，从根节点开始，每次访问一个节点，然后将该节点的值加到目标和上，若该节点为叶子节点，则判断目标和是否等于该节点的值，若不是叶子节点，则继续递归访问它的子节点，直到找到叶子节点，然后判断目标和是否等于叶子节点的值。

def hasPathSum(self, root, sum):
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)

2.2、迭代法

迭代法是指，从根节点开始，每次访问一个节点，然后将该节点的值加到目标和上，若该节点不是叶子节点，则将该节点的子节点入队，若该节点是叶子节点，则判断目标和是否等于该节点的值，然后继续出队访问下一个节点，直到队列为空，此时结束遍历。

def hasPathSum(self, root, sum):
if not root:
return False
queue = [(root, root.val)]
while queue:
node, val = queue.pop(0)
if not node.left and not node.right and val == sum:
return True
if node.left:
queue.append((node.left, val + node.left.val))
if node.right:
queue.append((node.right, val + node.right.val))
return False

3、总结

以上是LeetCode树路径总和问题的两种解决方案，递归法和迭代法，它们的思路都是从根节点开始，每次访问一个节点，然后将该节点的值加到目标和上，若该节点不是叶子节点，则继续访问它的子节点，若是叶子节点，则判断目标和是否等于该节点的值。