湘潭网站制作公司,网站做排行多少费用,wordpress 获取父页面,wordpress安装 windows给你二叉树的根节点 root 和一个整数目标和 targetSum #xff0c;找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。 叶子节点 是指没有子节点的节点。 在这里给大家提供两种方法进行思考#xff0c;第一种方法是递归#xff0c;第二种方式使用回溯的方式进行爆… 给你二叉树的根节点 root 和一个整数目标和 targetSum 找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。 叶子节点 是指没有子节点的节点。 在这里给大家提供两种方法进行思考第一种方法是递归第二种方式使用回溯的方式进行爆搜 递归树具有天然的递归结构将一个大的问题转换成多个相同的子问题而进行解决就相当于你会0-1的算式你自然而然可以推导出0-n的算式递归终止条件递归操作 我觉的这个图可以很形象的说明一些问题通过改变每个结点的差值最后进行叶子结点与传入的target进行比较如果相等就说明树中肯定有满足情况的路径
解题步骤
方法中返回什么我们就创建什么 public ListListInteger pathSum(TreeNode root, int targetSum) {ListListInteger resListnew LinkedList();...}
递归结束的条件分为第一次入参和叶子结点的入参两者的操作不一样 //如果传进行的叶子结点为空直接返回一个空链表if(rootnull){return resList;}//如果是叶子结点且叶子结点的值等于target,则该叶子结点是满足情况下的一条路径上的值if(root.leftnullroot.rightnull){if(root.valtargetSum){ListInteger listnew LinkedList();list.add(root.val);//将该路径加入总结果集中resList.add(list);}return resList;}
每次递归的时候将target-root.val作为参数传下去
int difftargetSum-root.val;
如果左树不为空递归左树如果右树不为空递归右树 if(root.left!null){ListListInteger curListpathSum(root.left,diff);for(int i0;icurList.size();i){ListInteger list1curList.get(i);//将该节点加入路径中list1.add(0,root.val);//加入到结果集中resList.add(list1);}}if(root.right!null){ListListInteger curListpathSum(root.right,diff);for(int i0;icurList.size();i){ListInteger list1curList.get(i);list1.add(0,root.val);resList.add(list1);}}
最后每次递归结束后返回结果集供归的时候进行使用
return resList;
方法二回溯
回溯的方法相当于暴力搜索一样但是对于面试而言我更加推荐回溯比较容易记忆 //大体思想其实和递归差不多就是回溯这种题有个特定的模板有的时候即使你不会做那你也有可能把题做出来ListListInteger resListnew LinkedList();ListInteger pathnew LinkedList();public ListListInteger pathSum(TreeNode root, int targetSum) {if(rootnull){return resList;}backtracing(root,targetSum);return resList;}public void backtracing(TreeNode root,int targetSum){if(rootnull){return;}path.add(root.val);if(targetSumroot.valroot.leftnullroot.rightnull){resList.add(new ArrayList(path));}int difftargetSum-root.val;if(root.left!null){pathSum(root.left,diff);//回溯path.remove(path.size()-1);}if(root.right!null){pathSum(root.right,diff);path.remove(path.size()-1);}}
