剑指offer系列之二十三：二叉树中和为某一值得所有路径

题目描述

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

由于是从根节点开始遍历的，所以自然联想到前序遍历，但是问题并没有那么简单，在遍历的过程中需要记录遍历的所有节点值的和，当某条路径遍历完毕之后，还需要切换到另一个节点，比如从某个节点的左孩子切换到右孩子，然后需要重新计算总和，并且需要减去原来那个节点的值。大概思路是：使用前序遍历的方式，如果遍历到叶子节点，和恰好是目标值，那么就将遍历经过的所有节点放在一个集合中。如果遍历到叶子节点仍然不等于目标值，那么就切换到节点的右孩子节点重新计算（需要移除集合中添加的节点，并重新计算所有节点集合中的和）；如果没有遍历到叶子节点就从其孩子节点中继续寻找这样的路径。

基于这样的思路，写出如下代码（已被牛客AC）：

package com.rhwayfun.offer;

import java.util.ArrayList;

public class FindTreePath {

    static class TreeNode {
        int val = 0;
        TreeNode left = null;
        TreeNode right = null;

        public TreeNode(int val) {
            this.val = val;

        }

    }

    public ArrayList<ArrayList<Integer>> FindPath(TreeNode root, int target) {
        int currentSum = 0;
        ArrayList<Integer> pathNodes = new ArrayList<Integer>();
        ArrayList<ArrayList<Integer>> pathList = new ArrayList<ArrayList<Integer>>();
        if(root == null) return pathList;
        return FindPath(pathList,pathNodes,root,target,currentSum);
    }

    private ArrayList<ArrayList<Integer>> FindPath(
            ArrayList<ArrayList<Integer>> pathList,
            ArrayList<Integer> pathNodes,
            TreeNode root,
            int target,
            int currentSum) {

        currentSum += root.val;
        pathNodes.add(root.val);

        //如果是是叶子结点且和等于目标值，则把当前的路径添加到pathList中
        boolean isLeafNode = root.left == null && root.right == null;
        if(currentSum == target && isLeafNode){
            ArrayList<Integer> nodes = new ArrayList<Integer>();
            //遍历pathNodes集合
            for (Integer val : pathNodes) {
                nodes.add(val);
            }
            pathList.add(nodes);
        }

        //如果不是叶子节点，就从其孩子节点寻找
        if(root.left != null){
            FindPath(pathList,pathNodes, root.left, target, currentSum);
        }
        if(root.right != null){
            FindPath(pathList, pathNodes,root.right, target, currentSum);
        }

        //在返回父节点只之前，需要删除当前节点
        Integer val = pathNodes.remove(pathNodes.size() - 1);
        currentSum -= val;
        return pathList;
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(10);
        TreeNode node1 = new TreeNode(5);
        TreeNode node2 = new TreeNode(12);
        TreeNode node3 = new TreeNode(4);
        TreeNode node4 = new TreeNode(7);

        root.left = node1;
        root.right = node2;
        node1.left = node3;
        node1.right = node4;

        ArrayList<ArrayList<Integer>> list = new FindTreePath().FindPath(null, 0);
        System.out.println("大小：" + list.size());
        for (ArrayList<Integer> arrayList : list) {
            for (Integer integer : arrayList) {
                System.out.print(integer + " ");
            }
            System.out.println();
        }
    }
}