검지offer 시리즈의 23: 두 갈래 나무 중 하나는 모든 경로가 될 만한

제목 설명
두 갈래 트리와 정수를 입력하고 두 갈래 트리의 결점 값과 정수를 입력하기 위한 모든 경로를 출력합니다.경로는 나무의 뿌리 결점에서 시작하여 잎 결점까지 내려가는 결점으로 경로를 형성합니다.
루트 노드에서 시작하여 훑어보았기 때문에 자연스럽게 앞의 훑어보는 것을 연상하지만 문제는 그리 간단하지 않다. 훑어보는 과정에서 훑어보는 모든 노드 값의 합을 기록해야 한다. 어떤 경로가 훑어본 후에 다른 노드로 전환해야 한다. 예를 들어 어떤 노드의 왼쪽 아이에서 오른쪽 아이로 전환한 다음에 총계를 다시 계산하고 원래의 노드 값을 줄여야 한다.대략적인 사고방식은 앞의 순서를 두루 훑어보는 방식을 사용한다. 만약에 잎 노드를 두루 훑어보고 목표치라면 두루 훑어보는 모든 노드를 하나의 집합에 놓는다.만약 잎사귀 노드를 두루 훑어봐도 목표 값이 같지 않으면 노드의 오른쪽 아이 노드로 전환해서 다시 계산합니다(집합에 추가된 노드를 제거하고 모든 노드 집합의 합을 다시 계산해야 합니다).잎사귀 노드를 두루 돌아다니지 않았다면 아이의 노드에서 이런 경로를 계속 찾았을 것이다.
이러한 사고방식을 바탕으로 다음과 같은 코드를 작성합니다(이미 소객 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();
        }
    }
}