剑指offer：二叉树中和为某一值的路径

我不是女神ヾ 2021-06-24 16:09 286阅读 0赞

**试题：**  
输入一颗二叉树的跟节点和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。(注意: 在返回值的list中，数组长度大的数组靠前)  
**代码：**  
首先肯定要使用DFS来搜索树，为了保存路径上的节点，我们需要在搜索的过程中就保存节点访问值。一个巧妙之处在于当我们搜索完一个路径后递归返回时我们可以将保存的节点值删除来重新访问下一条路径。还有就是如何计算路径的总和，利用减法将剩余值传入函数。

import java.util.ArrayList;
    /**
    public class TreeNode {
        int val = 0;
        TreeNode left = null;
        TreeNode right = null;
    
        public TreeNode(int val) {
            this.val = val;
    
        }
    
    }
    */
    public class Solution {
        private ArrayList<ArrayList<Integer>> allList = new ArrayList<ArrayList<Integer>>();
        private ArrayList<Integer> list = new ArrayList<Integer>();
        public ArrayList<ArrayList<Integer>> FindPath(TreeNode root,int target) {
            if(root==null) return allList;
            
            list.add(root.val);
            target -= root.val;
            if(target==0 && root.left==null && root.right==null)
                allList.add(new ArrayList<Integer>(list)); //防止引用
            FindPath(root.left, target);
            FindPath(root.right, target);
            list.remove(list.size()-1);
            return allList;
        }
    }