题目
给你二叉树的根节点 root 和一个表示目标和的整数 targetSum ，判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和 targetSum 。
叶子节点 是指没有子节点的节点。
示例 1
输入：root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22 输出：true
示例 2：
输入：root = [1,2,3], targetSum = 5 输出：false
示例 3：
输入：root = [1,2], targetSum = 0 输出：false
解题
方法一：广度优先搜索
利用BFS，创建两个队列，一个队列放节点，一个队列放到该节点的路径之和
python解法
# Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution: def hasPathSum(self, root: TreeNode, targetSum: int) -> bool: if not root: return False queue_node = [root] queue_val = [root.val] while queue_node: l = len(queue_node) for _ in range(l): cur = queue_node.pop(0) tmp = queue_val.pop(0) left,right=cur.left,cur.right if (not (left or right)) and tmp==targetSum: return True if left: queue_node.append(left) queue_val.append(left.val+tmp) if right: queue_node.append(right) queue_val.append(right.val+tmp) return False
当然也可以将 节点和到该节点的路径总和 组成一个元组，放在一个队列里。
# Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution: def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool: if not root: return False queue = [(root,root.val)] while queue: l = len(queue) for _ in range(l): cur,val = queue.pop(0) left,right = cur.left,cur.right if val==targetSum and not (left or right): return True if left: queue.append((left,val+left.val)) if right: queue.append((right,val+right.val)) return False
c++解法
class Solution { public: bool hasPathSum(TreeNode* root, int targetSum) { if(!root) return false; queue<TreeNode*> queue_node; queue<int> queue_val; queue_node.push(root); queue_val.push(root->val); while(!queue_node.empty()){ TreeNode* cur=queue_node.front(); queue_node.pop(); int val=queue_val.front(); queue_val.pop(); if(!(cur->left||cur->right)&&val==targetSum){ return true; } if(cur->left){ queue_node.push(cur->left); queue_val.push(val+cur->left->val); } if(cur->right){ queue_node.push(cur->right); queue_val.push(val+cur->right->val); } } return false; } };
将节点和路径长度pair在一起.
class Solution { public: bool hasPathSum(TreeNode* root, int targetSum) { if(!root) return false; queue<pair<TreeNode*,int>> queue; queue.push(pair<TreeNode*,int>(root,root->val)); while(!queue.empty()){ pair<TreeNode*,int> node=queue.front(); queue.pop(); if(!node.first->left&&!node.first->right&&node.second==targetSum){ return true; } if(node.first->left){ queue.push(pair<TreeNode*,int>(node.first->left,node.second+node.first->left->val)); } if(node.first->right){ queue.push(pair<TreeNode*,int>(node.first->right,node.second+node.first->right->val)); } } return false; } };
方法二：堆栈
其实有点像广度优先搜索，但是用堆栈代替了队列，因为pop(0)和pop()尾部，都一样，每个节点最终都会被遍历到，每个节点的路径和也与遍历的方式无关。
同样的方式，利用两个堆栈，一个放节点，一个放到该节点的路径和
# Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution: def hasPathSum(self, root: TreeNode, targetSum: int) -> bool: if not root: return False stack = [root] stack_val = [root.val] while stack: cur = stack.pop() tmp = stack_val.pop() if not (cur.left or cur.right) and tmp==targetSum: return True if cur.left: stack.append(cur.left) stack_val.append(tmp+cur.left.val) if cur.right: stack.append(cur.right) stack_val.append(tmp+cur.right.val) return False
方法三：递归回溯
java
class Solution { boolean dfs(TreeNode node,int sum,int targetSum){ if(node.left==null&&node.right==null&&sum+node.val==targetSum) return true; if(node.left!=null){ if(dfs(node.left,sum+node.val,targetSum)) return true; } if(node.right!=null){ if(dfs(node.right,sum+node.val,targetSum)) return true; } return false; } public boolean hasPathSum(TreeNode root, int targetSum) { if(root==null) return false; return dfs(root,0,targetSum); } }
或者
class Solution { boolean dfs(TreeNode root,int sum,int targetSum){ if(root.left==null&&root.right==null&&sum==targetSum) return true; if(root.left!=null){ if(dfs(root.left,sum+root.left.val,targetSum)) return true; } if(root.right!=null){ if(dfs(root.right,sum+root.right.val,targetSum)) return true; } return false; } public boolean hasPathSum(TreeNode root, int targetSum) { if(root==null) return false; return dfs(root,root.val,targetSum); } }
