题解 | #二叉树中和为某一值的路径#

题目描述

输入一颗二叉树的根节点和一个整数，按字典序打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。
示例1
输入：{10,5,12,4,7},22
返回值：[[10,5,7],[10,12]]

题目分析

路径定义为从树的根结点开始往下直到叶子结点所经过的结点形成一条路径。
将根结点到叶子结点之间所有结点的值相加为路径的值，要求二叉树中满足条件的所有路径，则需要遍历所有可能的路径，若符合条件则加入结果中。
如示例1：{10,5,12,4,7},22

满足目标和为22的有两条路径：
[[10,5,7],[10,12]]

解题思路

对二叉树的所有路径的遍历，就是二叉树的深度遍历（DFS），我们需要在遍历的过程中记录当前路径上的值list，以及它们的和sum，当遍历到叶子节点时，这条路径已经完成，若和等于target则加入结果路径中。
二叉树的DFS过程就是先序遍历的过程
二叉树的DFS代码框架如下：

dfs(root, target, sum){
  // 操作root，记录路径结点值
  list.add(root.val);
  sum += root.val;
  if(root 是叶子结点 && sum == target) return true;
  // 递归root的left;
  dfs(root.left, target, sum);
  // 递归root的right;
  dfs(root.right, target, sum);
}

具体在实现时，需要考虑root是否为空等条件。

代码实现

树的DFS一般使用递归来实现，在下面的代码中，使用全局成员变量res存储所有路径，path存储当前路径上的结点值，在计算当前路径和时，没有使用相加的方式，而是通过让（target-当前结点值），最后判断剩下的值是否是叶子结点的值即可，更加简单方便。

    ArrayList<arraylist<integer>> res = new ArrayList<>();
    ArrayList<integer> path = new ArrayList<>();
    public ArrayList<arraylist<integer>> FindPath(TreeNode root,int target) {
        if (root == null) {
            return res;
        }
        findPath(root, target);
        return res;
    }
    public void findPath(TreeNode root, int target) {
        //因为FindPath中和 下面程序中都进行了判null操作，root绝对不可能为 null
        path.add(root.val);
        //已经到达叶子节点，并且正好加出了target
        if (root.val == target && root.left == null && root.right == null) {
            //将该路径加入res结果集中
            res.add(new ArrayList(path));
        }
        //如果左子树非空，递归左子树
        if (root.left != null) {
            findPath(root.left, target - root.val);
        }
        //如果右子树非空，递归右子树
        if (root.right != null) {
            findPath(root.right, target - root.val);
        }
        //无论当前路径是否加出了target，必须去掉最后一个，然后返回父节点，去查找另一条路径，最终的path肯定为null
        path.remove(path.size() - 1);
        return;
    }

在递归的过程中，遍历了树的所有结点，所以时间复杂度为O(n);
递归的深度最多为n，空间复杂度为O(n)。