phpcms 网站打不开,服务公司沈傲芳,全球搜怎么样,sq网站推广目录112. 路径总和题目递归解递归解#xff0c;其他人的解法迭代解#xff0c;其他人的解法113. 路径总和 II题目递归解递归解#xff0c;参考别人的思路112. 路径总和
题目
给定一个二叉树和一个目标和#xff0c;判断该树中是否存在根节点到叶子节点的路径#xff0c;…
目录112. 路径总和题目递归解递归解其他人的解法迭代解其他人的解法113. 路径总和 II题目递归解递归解参考别人的思路112. 路径总和
题目
给定一个二叉树和一个目标和判断该树中是否存在根节点到叶子节点的路径这条路径上所有节点值相加等于目标和。
说明: 叶子节点是指没有子节点的节点。
示例: 给定如下二叉树以及目标和 sum 22 返回 true, 因为存在目标和为 22 的根节点到叶子节点的路径 5-4-11-2。
递归解
1、函数参数当前树的根结点、当前累积的路径和目标路径和返回值为空 2、终止条件该结点为空 3、单层逻辑如果该结点不为空则在累积路径和上加上该结点的值。如果该结点是叶子结点判断此时的累积路径和与目标路径和是否相同如果相同则将全局变量ifHas改为true认为能够找到路径和为目标值的路径。然后返回父结点回溯到上一个状态参数会自动更正为上一个状态的参数。接下来就是按顺序对该结点的左右孩子进行遍历
这个思路是有问题的因为它只在叶子结点之后才回溯这是不合理的但是也能AC。
/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode(int x) : val(x), left(NULL), right(NULL) {}* };*/
class Solution {
public:bool ifHasfalse;void traversal(TreeNode* cur,int target,int Mysum){if(curNULL) return;if(cur!NULL) Mysumcur-val;//如果是叶子结点则进行比较if(cur-leftNULL cur-rightNULL){//如果和目标结果相同if(Mysum target) ifHastrue;return;}if(cur-left){traversal(cur-left,target,Mysum);}if(cur-right){traversal(cur-right,target,Mysum);}return ;}bool hasPathSum(TreeNode* root, int sum) {//if(root NULL) return false;int Mysum0;traversal(root,sum,Mysum);return ifHas;}
};递归解其他人的解法
1、函数参数、返回值确定 之前有个结论如果需要搜索整棵二叉树那么递归函数就不要返回值如果要搜索其中一条符合条件的路径递归函数就需要返回值因为遇到符合条件的路径就要及时返回。 本题并不需要遍历整棵树所以递归函数需要返回值可以用bool类型表示。
bool traversal(TreeNode* cur,int count) 2、终止条件确定 在如何统计一条路径和的方法上代码随想录使用递减的方法让计数器count初始为目标和然后每次减去遍历路径结点上的数值。如果最后count0同时到了叶子结点的话说明了找到目标和。如果遍历到了叶子结点cout不为0就是没找到
if(!cur-left !cur-right count 0) return true; //遇到叶子结点并且计数为0
if(!cur-left !cur-right) return false; //遇到叶子结点没有找到合适的边直接返回3、确定单层递归的逻辑 因为终止条件是判断也自己诶单所以递归过程中就不要让空结点进入递归了。 递归函数的返回值为true的话说明了找到了合适的路径应该立刻返回
if(cur-left)
{count -cur-left-val;//遇到叶子结点返回true则直接返回trueif(traversal(cur-left,count)) return true;count cur-left-val; //回溯撤销处理结果
}
if(cur-right)
{count -cur-right-val;//遇到叶子结点返回true则直接返回trueif(traversal(cur-right,count)) return true;count cur-right-val; //回溯撤销处理结果
}
return false;class Solution {
public:bool traversal(TreeNode* cur,int count) {if(!cur-left !cur-right count 0) return true; //遇到叶子结点并且计数为0if(!cur-left !cur-right) return false; //遇到叶子结点没有找到合适的边直接返回if(cur-left){count -cur-left-val;//遇到叶子结点返回true则直接返回trueif(traversal(cur-left,count)) return true;count cur-left-val; //回溯撤销处理结果}if(cur-right){count -cur-right-val;//遇到叶子结点返回true则直接返回trueif(traversal(cur-right,count)) return true;count cur-right-val; //回溯撤销处理结果}return false;}bool hasPathSum(TreeNode* root, int sum) {if(root NULL) return false;return traversal(root,sum-root-val);}
};迭代解其他人的解法
如果使用栈模拟递归的话对于回溯如何处理 此时栈里面的一个元素不仅要记录该结点指针还要记录从头结点到该结点的路径数值总和。 这里使用pair结构来存放栈里面的元素。第一次用这个结构 定义为 pairTreeNode*,int pair结点指针路径数值 为栈中的一个元素。 使用栈模拟前序遍历;
/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode(int x) : val(x), left(NULL), right(NULL) {}* };*/
class Solution {
public:bool hasPathSum(TreeNode* root, int sum) {if(root NULL) return false;//此时栈里面要放的是pair结点指针路径数值stackpairTreeNode*,int st;st.push(pairTreeNode*,int(root,root-val));while(!st.empty()){pairTreeNode*,int node st.top();st.pop();//如果这个结点是叶子结点同时该结点的路径数值等于sum那么就返回trueif(!node.first-left !node.first-right sum node.second ) return true;//右结点压进去一个结点的时候将该结点的路径数值也记录下来if(node.first-right){st.push(pairTreeNode*,int(node.first-right,node.secondnode.first-right-val));}//右结点压进去一个结点的时候将该结点的路径数值也记录下来if(node.first-left){st.push(pairTreeNode*,int(node.first-left,node.secondnode.first-left-val));}}return false;}
};113. 路径总和 II
题目
给定一个二叉树和一个目标和找到所有从根节点到叶子节点路径总和等于给定目标和的路径。
说明: 叶子节点是指没有子节点的节点。
递归解
同样的道理Mysum作为函数参数每次返回的时候会自动更正不需要手动回溯。 完成一次子结果就将子结果送入paths中。 path需要手动回溯。 path.push_back(cur-left-val);traversal(cur-left,target,Mysum);path.pop_back();同时需要注意在一开始要将根结点送入path中因为在我们的递归函数中只对左右孩子进行push_back()
class Solution {
public:vectorvectorint paths;vectorint path;void traversal(TreeNode* cur,int target,int Mysum){if(curNULL) return;if(cur!NULL){Mysumcur-val;} //如果是叶子结点则进行比较if(cur-leftNULL cur-rightNULL){//如果和目标结果相同if(Mysum target){paths.push_back(path);}return;}if(cur-left){path.push_back(cur-left-val);traversal(cur-left,target,Mysum);path.pop_back();}if(cur-right){path.push_back(cur-right-val);traversal(cur-right,target,Mysum);path.pop_back();}return ;}vectorvectorint pathSum(TreeNode* root, int sum) {if(rootNULL) return {};int Mysum0;path.push_back(root-val);traversal(root,sum,Mysum);return paths;}
};递归解参考别人的思路
/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode(int x) : val(x), left(NULL), right(NULL) {}* };*/
class Solution {
private:vectorvectorint paths;vectorint path;//递归函数不需要返回值因为我们要遍历整个树void traversal(TreeNode* cur,int count){if(!cur-left !cur-right count 0) //遇到了叶子结点且找到了和为sum的路径{paths.push_back(path);return;}if(!cur-left !cur-right ) return;if(cur-left){path.push_back(cur-left-val);count-cur-left-val;traversal(cur-left,count);countcur-left-val;path.pop_back();}if(cur-right){path.push_back(cur-right-val);count-cur-right-val;traversal(cur-right,count);countcur-right-val;path.pop_back();}return;}
public:vectorvectorint pathSum(TreeNode* root, int sum) {paths.clear();path.clear();if(rootNULL) return paths;path.push_back(root-val);traversal(root,sum-root-val);return paths;}
};工程实践上一定要clear但是由于力扣后台测试数据每次都是新new一个对象
