leetcode112.路径总和

本文主要是介绍leetcode112.路径总和，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

解法1是DFS，解法2是BFS
DFS应用了前序遍历的方法，BFS用的层序遍历求和，qt表示用队列存储树节点指针，qi表示存储到该节点的路径和

class Solution {
public:bool hasPathSum(TreeNode* root, int targetSum) {if(!root){return false;}bool flag=false;bool& exist=flag;// dfs(root,0,targetSum,exist);bfs(root,targetSum,exist);return exist;}void dfs(TreeNode* tn,int sum,int targetSum,bool& exist){if(!tn){return;}sum+=tn->val;if(sum==targetSum&&!tn->left&&!tn->right){exist=true;return;}dfs(tn->left,sum,targetSum,exist);dfs(tn->right,sum,targetSum,exist);}void bfs(TreeNode*node,int targetSum,bool& exist){if(!node){return;}if(!node->left&&!node->right){exist=targetSum==node->val;}queue<TreeNode*> qt;queue<int> qi;qt.push(node);qi.push(node->val);while(!qt.empty()){int sz=qt.size();for(int i=0;i<sz;++i){TreeNode* tn=qt.front();int sum=qi.front();if(tn->left){int sum1=tn->left->val+sum;if(!tn->left->left&&!tn->left->right&&sum1==targetSum){exist=true;return;}qt.push(tn->left);qi.push(sum1);}if(tn->right){int sum1=tn->right->val+sum;if(!tn->right->left&&!tn->right->right&&sum1==targetSum){exist=true;return;}qt.push(tn->right);qi.push(sum1);}qt.pop();qi.pop();}}}
};

这篇关于leetcode112.路径总和的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---