[每日一道小算法（三十三）] [树] 二叉树中和为某一值的路径（剑指offer）

缺乏、安全感 2023-07-05 11:50 33阅读 0赞

前言：  
行动将引导你迈向你所渴望的成功。

### 题目描述 ###

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

### 题目解析 ###

我们来分析一下这道题，树的问题一般都可以往递归的思路上想。  
我们先从根节点开始，用目标整数减去这个根节点的值，就是以后路径要相加所得值。开始往下走，遇到一个节点，就执行相减操作，直到目标值为0并且到达了叶子节点，则符合条件，则退回到上一节点，去其他路径继续做相同的操作。根据这个我们可以进行递归来写这个代码。

### 代码样例 ###

private static ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
        private static ArrayList<Integer> list = new ArrayList<Integer>();
        public static ArrayList<ArrayList<Integer>> FindPath(TreeNode root,int target)
        { 
            if(root == null || target< 0)
            { 
                return result;
            }
            //保存到列表中
            list.add(root.val);
            target -=root.val;
            if(target == 0 && root.right==null && root.left == null)
            { 
                result.add(new ArrayList<Integer>(list));
            }
            FindPath(root.left,target);
            FindPath(root.right,target);
            list.remove(list.size()-1);
            return result;
        }
    
        public static void main(String[] args) { 
            TreeNode root = new TreeNode(10);
            root.left = new TreeNode(5);
            root.left.left = new TreeNode(4);
            root.left.right = new TreeNode(7);
            root.right = new TreeNode(12);
            ArrayList<ArrayList<Integer>> s1 = FindPath(root,22);
            for (ArrayList<Integer> s:s1
                 ) { 
                System.out.println(s);
            }
        }