悬赏修改问题代码:剑指offer“二叉树中和为某一值的路径”

各位大佬们好,我在做《剑指offer》题目“二叉树中和为某一值的路径”时,遇到问题,我的代码老是不能得到正确的答案。
我的问题代码如下,本想用左神的“暴力递归”的思路来解决这个问题,但在设计递归的时候出现了问题,得不到正确答案。
请大佬帮我看看,如果能修改好我的代码,附上解析,感激不尽~1000币拿走~

最新:
此题已解决,感激 断线风筝☆   的有效回答~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 但像数组、对象这类数据就不一样,它们被压栈的始终是地址,就算返回到上一个层级,数组中的变化内容也不会发生变化!
 这是很好的特点,可以用数组、对象等非基础类型的参数来保存中间的变量。
#笔试题目#
全部评论
import java.util.ArrayList; public class BinarySumII {     private static ArrayList<Integer> list=new ArrayList<Integer>();     private static ArrayList<ArrayList<Integer>> lists=new ArrayList<ArrayList<Integer>>();     public static ArrayList<ArrayList<Integer>> findPath(TreeNode root,int target){         if (root==null){             return lists;         }         target-=root.val;         list.add(root.val);         if (target==0&&root.left==null&&root.right==null){             int i=0;             while (i<lists.size()&&list.size()<lists.get(i).size()){                 i++;             }             lists.add(i,new ArrayList<>(list));         }else {             findPath(root.left,target);             findPath(root.right,target);         }         list.remove(list.size()-1);         return lists;     } //这是我的代码,简单的递归,注意最后要  list.remove(list.size()-1);如果没找到,则删除,牛客还要求要路径长的放在前面,所以简单判断一下就ok了。
3 回复
分享
发布于 2020-02-17 13:59
帮你顶一下2333
3 回复
分享
发布于 2020-02-17 14:28
百信银行
校招火热招聘中
官网直投
帮顶~
2 回复
分享
发布于 2020-02-17 14:34
悬赏吸引了我 奈何看不懂java
1 回复
分享
发布于 2020-02-17 12:44
后序遍历 然后再维护一个list 然后再加点判断应该就没问题了  看了几个关键代码 感觉应该没啥大问题吧
1 回复
分享
发布于 2020-02-17 17:38
土豪啊。。悬赏100块钱。
1 回复
分享
发布于 2020-02-17 17:43
这个方法看起来复杂了 不如试试回溯法 有时候可以换个思路(你的二叉表节点的构造函数没有为左右节点赋值为null)
点赞 回复
分享
发布于 2020-02-17 17:28

相关推荐

点赞 评论 收藏
转发
3 2 评论
分享
牛客网
牛客企业服务