112. 路径总和

力扣题目链接(opens new window)

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

说明: 叶子节点是指没有子节点的节点。

示例: 给定如下二叉树，以及目标和 sum = 22，

返回 true, 因为存在目标和为 22 的根节点到叶子节点的路径 5->4->11->2;

class Solution {
public:bool hasPathSum(TreeNode* root, int targetSum) {queue<TreeNode*>node_que;queue<int>val_que;if(!root) return false;node_que.push(root);val_que.push(root->val);while(!node_que.empty()){TreeNode* node = node_que.front();node_que.pop();int tmp = val_que.front();val_que.pop();if(!node->left && !node->right){if(tmp == targetSum) return true;}if(node->left){node_que.push(node->left);val_que.push(tmp + node->left->val);}if(node->right){node_que.push(node->right);val_que.push(tmp + node->right->val);}}return false;}
};

//dfs 

class Solution {
public:bool dfs(TreeNode* root,int count){if(!root) return false;if(!root->left && !root->right && count == 0) return true;if(!root->left && !root->right) return false;if(root->left){count -= root->left->val;if(dfs(root->left,count)) return true;//由子树的情况反映给父节点，如果true，一路上传给根节点。否则一路上传false。count += root->left->val; // 回溯隐藏在递归后面}if(root->right){count -= root->right->val;if(dfs(root->right,count)) return true;count += root->right->val; }return false;}bool hasPathSum(TreeNode* root, int targetSum) {//dfsif(!root) return false;return dfs(root,targetSum-root->val);}
};