검지offer의 면접문제 25: 두 갈래 나무와 어떤 값의 경로

제목 설명
두 갈래 트리와 정수를 입력하고 두 갈래 트리의 결점 값과 정수를 입력하기 위한 모든 경로를 출력합니다.경로는 나무의 뿌리 결점에서 시작하여 잎 결점까지 내려가는 결점으로 경로를 형성합니다.
예를 들어 분석해보겠습니다.

            10
           /  \           5   12
         / \  
        4  7 

과 22의 경로는 두 가지가 있습니다. {10, 5, 7}, {10, 12}
어떻게 얻었어요?먼저 모든 결점을 훑어보아야 한다. (경로 정의는 뿌리 결점에서 잎 결점까지 지나가는 결점이 형성된 경로이기 때문에 먼저 뿌리 결점을 훑어보아야 한다. 두 갈래 나무의 앞차례 훑어보기, 중차례 훑어보기, 뒷차례 훑어보기 중 앞차례 훑어보기만 일치한다.)두 갈래 나무는 아버지의 결점을 가리키는 지침이 없기 때문에 매번 결점을 지나갈 때마다 임시 변수에 저장해야 한다.잎 결점까지 두루 다니며 임시 결점이 형성하는 경로의 합을 계산하고 충족되면 이 경로를 저장합니다 (경로가 한 개가 아닙니다).만약 만족스럽지 않다면 하나씩 결점을 제거하고 아버지 노드로 돌아간 다음에 오른쪽 아이로 전환하여 경로와 아직 만족스럽지 않다면 할아버지 결점을 거슬러 올라가..., 귀속한다.
단계
조작하다
잎결점 여부
경로
경로 결점 값의 및
일
액세스 결점 10
아니오
{10}
십
이
액세스 결점 5
아니오
{10,5}
십오
삼
액세스 종료 4
예.
{10,5,4}
19, 잎사귀 결점 그러나 부합되지 않음, 제거 4
사
결점으로 돌아가기 5
{10,5}
십오
오
액세스 종료 7
예.
{10,5,7}
22, 잎사귀 결점 일치, 경로 저장
육
결점으로 돌아가기 5
{10,5}
십오
칠
결점 10으로 돌아가기
{10}
십
팔
액세스 종료 12
{10,12}
22, 잎사귀 결점 일치, 경로 저장
요약: 앞의 순서가 어떤 결점을 두루 훑어보고 결점을 경로에 추가하고 경로의 현재 값의 합을 계산합니다. 만약에 현재 결점이 잎 결점이고 정확하게 입력한 값이라면 요구에 따라 경로를 저장합니다.잎사귀 결점이 아니라면 아이를 계속 방문하세요.현재 결점 접근이 끝나면 귀속 함수는 자동으로 부모 결점으로 돌아가며 그 전에 현재 결점과 결점 값을 제거합니다.사실 이것이 바로 귀속잔의 압입과 출잔이다.
코드는 다음과 같습니다.

/** * */
package com.su.biancheng;

import java.util.ArrayList;


/** * @title FindPath.java * @author Shuai * @date 2016-4-27 4:43:13 */
public class FindPath {
    public static class TreeNode {
        int val = 0;
        TreeNode left = null;
        TreeNode right = null;

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

        }
    }
    public static ArrayList<ArrayList<Integer>> FindPath(TreeNode root, int target) {
        ArrayList<ArrayList<Integer>> list=new ArrayList<ArrayList<Integer>>();
        if(root==null)
            return list;
        ArrayList<Integer> path=new ArrayList<Integer>();
        int currentSum=0;
        return FindPath(root,target,list,path,currentSum);
    }
    public static ArrayList<ArrayList<Integer>> FindPath(TreeNode root,
            int target, ArrayList<ArrayList<Integer>> list, ArrayList<Integer> path, int currentSum) {
        currentSum += root.val;
        path.add(root.val);

        // ， list 
        boolean isLeafNode = root.left == null && root.right == null;
        if(currentSum == target && isLeafNode){
            ArrayList<Integer> nodes = new ArrayList<Integer>();
            // path 
            for (Integer val : path) {
                nodes.add(val);
            }
            list.add(nodes);
        }

        // ， 
        if(root.left != null){
            FindPath(root.left,target,list,path,currentSum);
        }
        if(root.right != null){
            FindPath(root.right,target,list,path,currentSum);
        }

        // ， 
        Integer val = path.remove(path.size() - 1);
        currentSum -= val;
        return list;
    }
    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;

        System.out.println(FindPath(root,22).toString());
    }
}