悬赏修改问题代码:剑指offer“二叉树中和为某一值的路径”
各位大佬们好,我在做《剑指offer》题目“二叉树中和为某一值的路径”时,遇到问题,我的代码老是不能得到正确的答案。
我的问题代码如下,本想用左神的“暴力递归”的思路来解决这个问题,但在设计递归的时候出现了问题,得不到正确答案。
请大佬帮我看看,如果能修改好我的代码,附上解析,感激不尽~1000币拿走~
最新:
1 问题代码如下:
import org.junit.Test; import java.util.ArrayList; class TreeNode { int val = 0; TreeNode left = null; TreeNode right = null; public TreeNode(int val) { this.val = val; } } public class Solution { public ArrayList<ArrayList<Integer>> FindPath(TreeNode root,int target) { int deepNum=1;//当前的深度 ArrayList<Integer> depths=new ArrayList<Integer>(); ArrayList<Integer> singlePath=new ArrayList<Integer>(); ArrayList<ArrayList<Integer>> paths=new ArrayList<ArrayList<Integer>>(); if(root==null)return paths; if(root!=null){ singlePath.add(root.val);//把最初的节点加入临时路径 depths.add(1);//把最初的深度加进去 } boolean ifOk=false;//某条路径是否符合要求的标志 process(root,deepNum,depths,singlePath,paths,target,ifOk); System.out.println("OK了,下面单独进行排序~"); /*排序代码,路径长的在前面*/ return paths; }//(修改的时候,参数名称,数量尽量保持不变)@Test//测试代码,需要导入 public static void main(String[] args){ TreeNode root=new TreeNode(1); root.left=new TreeNode(2); root.right=new TreeNode(3); root.left.left=new TreeNode(1); root.left.right=new TreeNode(2); FindPath(root,4); } //递归的部分 //(修改的时候,参数名称,数量尽量保持不变) public static void process(TreeNode root,//根节点 int deepNum,//当前来到的临时深度 ArrayList<Integer> depths,//记录符合标准的临时深度 ArrayList<Integer> singlePath,//某一条临时路径 ArrayList<ArrayList<Integer>> paths,//符合条件的路径 int target,//目标值 boolean ifOk//是否满足题意 ){ if(root==null){ deepNum--;//如果已经为空了,深度-1 int tempSum=0; for(int i=0;i<singlePath.size();i++){ tempSum+=singlePath.get(i); } ifOk=tempSum==target?true:false; if(ifOk){//符合条件的路径,记录下路径和深度信息 paths.add(singlePath); depths.add(deepNum); int j=singlePath.size(); for(int i=0;i<j;i++){//将临时路径清空 singlePath.remove(0); } } return; } boolean ifOk1=false,ifOk2=false;//分别指示左右路径是否满足题意 if(root.left!=null){ singlePath.add(root.left.val);//左结点不为空才加入临时路径 } process(root.left,deepNum+1,depths,singlePath,paths,target,ifOk1);//深度+1进入下一个递归 ArrayList<Integer> path1=new ArrayList<Integer>(singlePath);//左边路径 if(root.right!=null){ singlePath.add(root.right.val);//右结点不为空才加入临时路径 } process(root.right,deepNum+1,depths,singlePath,paths,target,ifOk2); ArrayList<Integer> path2=new ArrayList<Integer>(singlePath);//右边路径 } }
2.1 根据大佬断线风筝☆ 的修改结果如下:
import org.junit.Test; import java.util.ArrayList; public class Solution { private static ArrayList<Integer> depths=new ArrayList<Integer>(); private static ArrayList<Integer> singlePath=new ArrayList<Integer>(); private static ArrayList<ArrayList<Integer>> paths=new ArrayList<ArrayList<Integer>>(); public static ArrayList<ArrayList<Integer>> FindPath(TreeNode root,int target) { int deepNum=1;//当前的深度 if(root==null)return paths; if(root!=null){ //depths.add(1);//把最初的深度加进去 } boolean ifOk=false;//某条路径是否符合要求的标志 process(root,deepNum,depths,singlePath,paths,target,ifOk); System.out.println("OK了,已经寻找完毕并且排好了顺序~"); return paths; } //递归的部分 /*基础知识补充,递归返回时候: 1 基础数据类型由于是存在常量池的,返回的时候会初始化成上一层的值; 2 但像数组、对象这类数据就不一样,它们被压栈的始终是地址,就算返回到上一个层级,数组中的变化内容也不会发生变化! 这是很好的特点,可以用数组、对象等非基础类型的参数来保存中间的变量*/ public static void process(TreeNode root,//根节点 int deepNum,//当前来到的临时深度 ArrayList<Integer> depths,//记录符合标准的临时深度 ArrayList<Integer> singlePath,//某一条临时路径 ArrayList<ArrayList<Integer>> paths,//符合条件的路径 int target,//目标值 boolean ifOk//是否满足题意,这里不用它(如果需要用到它,最好转化成数组,不然递归返回时候,是记录不到临时变量的) ){ if (root==null){//这里单纯为处理叶子的左右结点,直接返回即可。 return;} target-=root.val;//返回上一级的时候,target为基础数据类型,递归返回后,自动初始化成上一级的状态。 singlePath.add(root.val); boolean ifOk1=false,ifOk2=false;//分别指示左右路径是否满足题意 if (target==0&&root.left==null&&root.right==null){//这个if主要判断是否已经到达叶子节点并且路径的和是否和target相等 int i=0; while (i<paths.size()&&singlePath.size()<paths.get(i).size()){//主要为了让路径长度长的放在paths前面 i++; } //每一次递归循环,只可能产生并放入一个答案! //ArrayList.add(index,element)函数:将element插入到index处,原来位置元素右移。 paths.add(i,new ArrayList<>(singlePath)); depths.add(i,deepNum);//存入路径的长度 }else {//下面决策时候,没有判断结点是否为空,留到递归函数最前面统一处理即可。 process(root.left,deepNum+1,depths,singlePath,paths,target,ifOk1); process(root.right,deepNum+1,depths,singlePath,paths,target,ifOk2); } //把某条尝试路径的最后一个元素去掉,返回上一层,进入上一层的另一个分支 singlePath.remove(singlePath.size()-1);// singlePath不属于基础数据类型,返回上一层并不会改变其状态!所以需要手动恢复初始状态! //deepNum--;//这里的代码是多余的,deepNum属于基本数据类型,返回时候,在上一层会直接被初始化。 } @Test//测试代码 public void test1(){ TreeNode root=new TreeNode(1); root.left=new TreeNode(2); root.right=new TreeNode(3); root.left.left=new TreeNode(1); root.left.right=new TreeNode(2); root.right.left=new TreeNode(4); root.right.right=new TreeNode(3); root.left.left.left=new TreeNode(2); root.left.right.left=new TreeNode(3); FindPath(root,6); } }2.2 少注释纯净版本
import java.util.ArrayList; public class Solution { private static ArrayList<Integer> depths=new ArrayList<Integer>(); private static ArrayList<Integer> singlePath=new ArrayList<Integer>(); private static ArrayList<ArrayList<Integer>> paths=new ArrayList<ArrayList<Integer>>(); public static ArrayList<ArrayList<Integer>> FindPath(TreeNode root,int target) { int deepNum=1; if(root==null)return paths; if(root!=null){ } boolean ifOk=false;//某条路径是否符合要求的标志 process(root,deepNum,depths,singlePath,paths,target,ifOk); System.out.println("OK了,已经寻找完毕并且排好了顺序~"); return paths; } public static void process(TreeNode root,int deepNum,ArrayList<Integer> depths, ArrayList<Integer> singlePath,ArrayList<ArrayList<Integer>> paths, int target,boolean ifOk){ if (root==null){return;} target-=root.val; singlePath.add(root.val); boolean ifOk1=false,ifOk2=false;//暂时不用 if (target==0&&root.left==null&&root.right==null){ int i=0; while (i<paths.size()&&singlePath.size()<paths.get(i).size()){ i++; } paths.add(i,new ArrayList<>(singlePath)); depths.add(i,deepNum);//存入路径的长度 }else { process(root.left,deepNum+1,depths,singlePath,paths,target,ifOk1); process(root.right,deepNum+1,depths,singlePath,paths,target,ifOk2); } singlePath.remove(singlePath.size()-1); } }
3 感激各位大佬帮助~谢谢~
补充知识点:
递归的部分基础知识补充,递归返回时候:
1 基础数据类型由于是存在常量池的,返回的时候会初始化成上一层的值;
2 但像数组、对象这类数据就不一样,它们被压栈的始终是地址,就算返回到上一个层级,数组中的变化内容也不会发生变化!
这是很好的特点,可以用数组、对象等非基础类型的参数来保存中间的变量。
1 基础数据类型由于是存在常量池的,返回的时候会初始化成上一层的值;
2 但像数组、对象这类数据就不一样,它们被压栈的始终是地址,就算返回到上一个层级,数组中的变化内容也不会发生变化!
这是很好的特点,可以用数组、对象等非基础类型的参数来保存中间的变量。