剑指Offer刷题笔记（Java）24——二叉树中和为某一值的路径

题目描述

输入一颗二叉树的根节点和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。(注意: 在返回值的list中，数组长度大的数组靠前)

解题思路

首先分析题目，可以明显看出这道题需要遍历每一条路径后选择出路径上所有值得和等于输入值的路径，所以本质是一个遍历二叉树的题目，遍历二叉树最好的方法就是递归，在这道题中，每次递归记录下当前节点值，当到叶子节点时判断所有节点和是否等于给定值，如果等于则判定该路径符合要求，存起来；而题目要求就数组长度打的数组靠前，因此每次加入一个新的序列时要判断路径的长度是否比前面的小。代码如下：

public class Solution {
    private ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
    private ArrayList<Integer> list = new ArrayList<>();
    public ArrayList<ArrayList<Integer>> FindPath(TreeNode root,int target) {
        if(root == null){
            return result;
        }
        list.add(root.val);
        target = target - root.val;
        if(target == 0 && root.left == null && root.right == null){
            result.add(new ArrayList<Integer>(list));
            for(int i=0;i<result.size();i++){
                for(int j=i;j>0;j--){
                    ArrayList<Integer> temp = new ArrayList<>();
                    if(result.get(j-1).size() < result.get(j).size()){
                        temp = result.get(j-1);
                        result.set(j-1,result.get(j)); 
                        result.set(j,temp);
                    }
                }
            }
        }
        FindPath(root.left, target);
        FindPath(root.right, target);
        list.remove(list.size()-1);
        return result;
    }
}

这里要注意当根节点为空的时候，不能直接返回list为空，因为递归过程中根是不断变化的，当前根为空不代表其他根也为空，因此返回list本身即可。

总结

这道题其实理解起来并不难，我思路来的很快但就是在实现上花了很多功夫，可能这种list里面套着另一个list的返回值让我有一些不知所措，但遇到问题要学会拆分的思想，理解了里面和外面的list分别是做什么用的，问题解决起来就快了很多。