二叉树路径和：递归与迭代求解策略
二叉树是数据结构中的一种，它由节点组成，每个节点最多有两个子节点：左子节点和右子节点。在二叉树中，路径和问题是一个经典的问题，它要求找出所有从根节点到叶子节点的路径，使得路径上所有节点的值之和等于一个特定的目标值。这个问题可以通过递归和迭代两种方法来解决。
本文将围绕二叉树路径和问题，分别介绍递归和迭代两种求解策略，并通过LeetCode上的相关题目来展示如何实现这些算法。
递归求解
递归是一种常用的算法设计方法，它通过将问题分解为更小的子问题来解决原问题。在二叉树路径和问题中，我们可以通过递归遍历树的每个节点，并检查从根节点到当前节点的路径和是否等于目标值。
以下是一个使用递归求解二叉树路径和的Python代码示例：
python
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def hasPathSum(root, targetSum):
if not root:
return False
if not root.left and not root.right:
return root.val == targetSum
return (hasPathSum(root.left, targetSum - root.val) or
hasPathSum(root.right, targetSum - root.val))
示例
构建二叉树
5
/
4 8
/ /
11 13 4
/ /
7 2 1
root = TreeNode(5)
root.left = TreeNode(4)
root.right = TreeNode(8)
root.left.left = TreeNode(11)
root.right.left = TreeNode(13)
root.right.right = TreeNode(4)
root.left.left.left = TreeNode(7)
root.right.left.left = TreeNode(2)
root.right.left.right = TreeNode(1)
检查路径和
print(hasPathSum(root, 22)) 输出：True
在上面的代码中，`hasPathSum` 函数通过递归检查每个节点，如果当前节点是叶子节点，则判断其值是否等于剩余的目标和。如果不是叶子节点，则递归检查左子树和右子树。
迭代求解
迭代求解通常使用栈或队列来实现，它通过手动维护路径和来遍历树。在二叉树路径和问题中，我们可以使用栈来模拟递归过程。
以下是一个使用迭代求解二叉树路径和的Python代码示例：
python
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def pathSum(root, targetSum):
if not root:
return []
stack = [(root, targetSum - root.val)]
result = []
while stack:
node, current_sum = stack.pop()
if not node.left and not node.right and current_sum == 0:
result.append([node.val])
if node.left:
stack.append((node.left, current_sum - node.left.val))
if node.right:
stack.append((node.right, current_sum - node.right.val))
return result
示例
构建二叉树
5
/
4 8
/ /
11 13 4
/ /
7 2 1
root = TreeNode(5)
root.left = TreeNode(4)
root.right = TreeNode(8)
root.left.left = TreeNode(11)
root.right.left = TreeNode(13)
root.right.right = TreeNode(4)
root.left.left.left = TreeNode(7)
root.right.left.left = TreeNode(2)
root.right.left.right = TreeNode(1)
检查路径和
print(pathSum(root, 22)) 输出：[[5, 4, 11, 2], [5, 8, 4, 5]]
在上面的代码中，`pathSum` 函数使用栈来遍历树，并记录每个节点的值。当遇到叶子节点且路径和等于目标值时，将当前路径添加到结果列表中。
LeetCode题目示例
LeetCode上有许多与二叉树路径和相关的题目，以下是一些示例：
1. 路径总和 II (https://leetcode.com/problems/path-sum-ii/)
2. 路径总和 III (https://leetcode.com/problems/path-sum-iii/)
3. 二叉树的所有路径 (https://leetcode.com/problems/binary-tree-paths/)
这些题目要求你实现不同的算法来找到满足条件的路径或节点。
总结
本文介绍了二叉树路径和问题的递归和迭代求解策略。递归方法简洁直观，但可能存在栈溢出的问题；迭代方法则更加灵活，可以避免栈溢出，但代码相对复杂。在实际应用中，可以根据具体问题和性能要求选择合适的求解方法。
通过LeetCode上的题目练习，可以加深对二叉树路径和问题的理解，并提高算法实现的技能。
Comments NOTHING