[数据结构与算法]JZ24 二叉树中和为某一值的路径

JZ17 二叉树中和为某一值的路径

描述

输入一颗二叉树的根节点和一个整数，按字典序打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。

示例1

输入：

{10,5,12,4,7},22

返回值：

[[10,5,7],[10,12]]

示例2

输入：

{10,5,12,4,7},15

返回值：

[]

解析

首先分析这道题的返回值，它是一个二维数组，其中的每个一维数组对应二叉树中的一条路径；即路径是一维数组，结果集是二维数组（又说了一遍😓）

	// 路径，一维数组
    private ArrayList<Integer> path = new ArrayList<>();
    // 结果集，二维数组
    private ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();

然后再进行过程的分析，本题的核心是二叉树的深度搜索，同时需要在到达某一点时判断路径上的值是否符合目标值，即过程为

1. 对二叉树进行深度优先遍历
2. 在遍历时记录到达当前节点的路径
3. 判断路径上的值是否符合目标值

同时，在判断路径是否符合目标值时，也有三种情况

1. 到当前节点时，路径值大于目标值，已经不符合条件，则直接返回，不用继续深入
2. 到当前节点时，正好达成目标值，则将当前路径加入结果集然后返回，不用继续深入（此处考虑本题的节点不包含0）
3. 到当前节点时，路径值小于目标值，则将当前节点加入路径后，继续遍历子节点

此外，还需要进行回溯操作，即遍历完某一节点下可能的路径后，要将其从路径中删除，这样才能正确地继续遍历该节点的兄弟节点！

代码清单

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<Integer> path = new ArrayList<>();
    // 结果集，二维数组
    private ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
    public ArrayList<ArrayList<Integer>> FindPath(TreeNode root,int target) {
        // 如果当前节点为空，即这条路走到底了，返回
        if(root == null) return result;
        // 用目标值减去当前节点值，查看是否满足
        target = target - root.val;
        // 走过头了，这个节点后面的路也不用走了
        if(target < 0)
            return result;
        // 将当前节点加入路径
        path.add(root.val);
        // 满足条件，且当前是叶子结点，这条路径就是正确的！
        if(target == 0 && root.left == null && root.right ==null){
            // 把当前的路径加入到结果集中
            // 此处不能直接 add(path)，要克隆一个出来！
            result.add(new ArrayList<Integer>(path));
            // 关键一步！
            // 通过删除当前路径中的当前节点，回溯到当前节点的父节点继续找！
            path.remove(path.size()-1);
            return result;
        }
        // 以上都不满足，说明 target > 0，继续走
        FindPath(root.left,target);
        FindPath(root.right,target);
        // 同理，返回前回溯到父节点
        path.remove(path.size()-1);
        return result;
    }
}

其中还遇到了一个问题，即将符合条件的路径加入结果集时，一开始使用的是

    result.add(path);

这样的话加入到结果集的是 path 本身，也就是说在修改 path 时 result 中的内容也会被改变，且如果加入两次，则这两次都是同一个path（可以理解为加进结果集的是指针）！

所以在将路径加入到结果集时，要克隆一个新的路径数组加进去，也就是上面的

    result.add(new ArrayList<Integer>(path));

此题终结！

总结

这题的本质还是树的遍历，但在遍历的基础上加入了寻找路径的目标，需要额外的数据结构来保存路径；同时需要对遍历中的情况进行判断，是继续遍历还是返回结果！