方法1:BFS
时间复杂度:O(n)
空间复杂度:O(n)
解题思路
根节点入队
循环步骤1-3直到队列为空
1. 节点出队
2. 节点的左子节点入队
3. 节点的右子节点入队
双队列,分别存储节点和该节点的路径总和
https://leetcode.cn/problems/path-sum/solution/lu-jing-zong-he-by-leetcode-solution/
Java 代码
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public boolean hasPathSum(TreeNode root, int targetSum) {
if (root == null) {
return false;
}
Queue<TreeNode> q1 = new LinkedList<>();
Queue<Integer> q2 = new LinkedList<>();
q1.offer(root);
q2.offer(root.val);
while (!q1.isEmpty()) {
TreeNode node = q1.poll();
int tmp = q2.poll();
if (node.left == null && node.right == null) {
if (tmp == targetSum) return true;
continue;
}
if (node.left != null) {
q1.offer(node.left);
q2.offer(tmp + node.left.val);
}
if (node.right != null) {
q1.offer(node.right);
q2.offer(tmp + node.right.val);
}
}
return false;
}
}