[LeetCode]Path Sum系列

1.二叉树路径求指定和，需要注意的是由于有负数，所以即使发现大于目标值也不能返回false，而且返回true的条件有两个，到叶节点且等于sum，缺一不可

public boolean hasPathSum(TreeNode root, int sum) {

        if (root==null) return false;

        if (root.val==sum&&root.left==null&&root.right==null) return true;

        else return hasPathSum(root.left,sum-root.val)||hasPathSum(root.right,sum- root.val);

    }

2.跟第一题的不同是要把所有路径返回，做法一样，把所有路径都遍历一遍，每次递归返回后都要回溯，把符合要求的路径记录

public List<List<Integer>> pathSum(TreeNode root, int sum) {

        List<List<Integer>> tp=new ArrayList<List<Integer>>();

        List<Integer> cu=new ArrayList<Integer>();

        int total=0;

        dfs(root, tp, cu,total,sum);

        return tp;

    }

    public void dfs(TreeNode root,List<List<Integer>> tp, List<Integer> cu,int total,int sum){

        if(root==null)

        return;

        cu.add(root.val);

        total=total+root.val;

        if(root.left==null&&root.right==null&&total==sum){

            tp.add(new ArrayList(cu));

            return;

        }

        if (root.left!=null){

            dfs(root.left,tp, cu,total,sum);

            cu.remove(cu.size()-1);

        }

        if (root.right!=null){

            dfs(root.right,tp, cu,total,sum);

            cu.remove(cu.size()-1);

        }

    }

3.不要求开头和结尾是根节点和叶节点，但是顺序必须自上而下，做法是递归的把所有节点都当做根节点判断一遍，每次判断时不同的地方是不用判断到没到叶节点，而且=target后不返回，只是结果+1，继续向下判断。

 public int pathSum(TreeNode root, int sum) {

        int cu=0;

        if (root == null)

            return 0;

        return dfs(root,sum,cu)+pathSum(root.left,sum)+pathSum(root.right,sum);

        // 开始的点不一定是根节点，采取的方法是返回根节点函数+左子节点函数+右子节点函数，这样递归后就可以实现所有节点都可以作为开始

    }

    public  int dfs(TreeNode root,int sum,int cu){

         int re=0;

         if (root == null)

            return re;

        cu+=root.val;

        if(cu == sum)

        re++;

        re+=dfs(root.left,sum,cu);

        re+=dfs(root.right,sum,cu);

        return re;

    }

巴特西

[LeetCode]Path Sum系列

最新文章

热门文章