# LeetCode 112: 路径总和 Path Sum

### 题目:

Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum.

Note: A leaf is a node with no children.

Given the below binary tree and `sum = 22`,

```              5
/ \
4   8
/   / \
11  13  4
/  \      \
7    2      1
```

return true, as there exist a root-to-leaf path `5->4->11->2` which sum is 22.

1. 当前层所有结点队列
2. 当前层所有结点的路径和

### 深度优先递归解法

##### 自顶向下的递归解法

Java:

```class Solution {
public boolean hasPathSum(TreeNode root, int sum) {
if (root == null) // 基线条件
return false;

sum -= root.val; // sum 逐层递减该层结点的结点值
if ((root.left == null) && (root.right == null)) // 如果是叶子结点
return (sum == 0); // 返回该路径是否满足条件
return hasPathSum(root.left, sum) || hasPathSum(root.right, sum);
}
}
```

Python:

```class Solution:
def hasPathSum(self, root: TreeNode, sum: int) -> bool:
if not root: # 基线条件
return False

sum -= root.val # sum 逐层递减该层结点的结点值
if not root.left and not root.right: # 如果是叶子结点
return (sum == 0) # 返回该路径是否满足条件
return self.hasPathSum(root.left, sum) or self.hasPathSum(root.right, sum)
```

### 广度优先迭代解法

Java:

```class Solution {
public boolean hasPathSum(TreeNode root, int sum) {
if (root == null)
return false;

Queue<TreeNode> queue_node = new LinkedList<>(); // 结点队列
Queue<Integer> queue_sum = new LinkedList<>(); // 路径和队列
int size = 0, tmp = 0;
TreeNode node;
while (!queue_node.isEmpty()) {
size = queue_node.size();
while (size-- > 0) {
node = queue_node.poll();
tmp = queue_sum.poll();
if (node.left == null && node.right == null && tmp == 0) // 叶子结点满足目标和时直接返回
return true;
if (node.left != null) {
}
if (node.right != null) {
}
}
}
return false;
}
}
```

Python:

```class Solution:
def hasPathSum(self, root: TreeNode, sum: int) -> bool:
if not root:
return False
queue_node = collections.deque() # 结点队列
queue_sum = collections.deque() # 路径和队列
queue_node.append(root)
queue_sum.append(sum-root.val) # 路径和队列存储的是差值
while queue_node:
size = len(queue_node)
while size > 0:
size -= 1
node = queue_node.popleft()
tmp = queue_sum.popleft()
if not node.left and not node.right and tmp == 0: # 叶子结点满足目标和时直接返回
return True
if node.left:
queue_node.append(node.left)
queue_sum.append(tmp-node.left.val)
if node.right:
queue_node.append(node.right)
queue_sum.append(tmp-node.right.val)
return False
```

0 条评论

• ### Leetcode 112 Path Sum

Given a binary tree and a sum, determine if the tree has a root-to-leaf path su...

• ### LeetCode 112. 路径总和

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

• ### [Leetcode][python]Path Sum II/路径总和 II

其实一开始不想项标准答案一样用函数嵌套，毕竟别的语言可能不支持，以后看答案不方便，但是如果把list_all放在全局，需要每轮都去清空它，而leetcode跑测...

• ### Leetcode No.112 路径总和

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

• ### LeetCode 113. 路径总和 II（回溯）

给定一个二叉树和一个目标和，找到所有从根节点到叶子节点路径总和等于给定目标和的路径。

• ### LeetCode笔记：112. Path Sum

image.png return true, as there exist a root-to-leaf path 5->4->11->2 which sum ...

• ### 【关关的刷题日记60】Leetcode 437. Path Sum III

关关的刷题日记60 – Leetcode 437. Path Sum III 题目 ? 题目的意思是给定一个二叉树，让我们找到路径节点和等于给定值的路径的个数。...

• ### 递归遍历-LeetCode 124、112、113（递归遍历二叉树，回溯法）

给定一个非空二叉树，返回其最大路径和。 本题中，路径被定义为一条从树中任意节点出发，达到任意节点的序列。该路径至少包含一个节点，且不一定经过根节点。

• ### 【关关的刷题日记58】Leetcode 112 Path Sum

关关的刷题日记58 – Leetcode 112 Path Sum 题目 ? 题目的意思是判断一棵二叉树跟到叶子节点的所有路径中是否有一条路径的和等于给定的和。...

• ### 15 道二叉树手写算法题（二）

在上一期讲到，树和链表的手写算法题在面试中出现的频率最高。也正是因为这样，如果你马上就要参加面试，但之前没有刷多少算法题，那么很建议你先看看树和链表相关的题目。...

• ### 天天算法 LeetCode-112-路径总和

https://leetcode-cn.com/problems/path-sum/

• ### ​LeetCode刷题实战112：路径总和

https://leetcode-cn.com/problems/path-sum/

• ### LeetCode 112&113&437 Path Sum I&II&III

Given a binary tree and a sum, determine if the tree has a root-to-leaf path suc...

• ### N皇后问题如何写出简洁的最优解 - 回溯法及LeetCode应用详解

回溯法之所以称之为回溯法，是因为它其实是DFS/BFS+回溯操作进行的穷举。回溯和DFS/BFS的区别在于回溯操作。也有人把回溯法称为BFS/DFS，这没有错，...

• ### 二叉树：递归函数究竟什么时候需要返回值，什么时候不要返回值？

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