이 진 트 리 와 특정한 값 의 경로

2392 단어 알고리즘
이 진 트 리 와 정 수 를 입력 하고 이 진 트 리 의 노드 값 과 정 수 를 입력 하기 위 한 모든 경 로 를 출력 합 니 다.경 로 는 나무의 뿌리 결점 에서 부터 잎 결점 이 지나 가 는 결점 까지 하나의 경 로 를 형성 하 는 것 으로 정의 된다.
도로 의 힘 은 뿌리 노드 부터 잎 노드 까지 의 통 로 를 말 하기 때문에 먼저 뿌리 노드 를 방문 해 야 한다. 몇 가지 나 무 를 옮 겨 다 니 는 방법 에서 앞 순 서 는 뿌리 - > 왼쪽 - > 오른쪽 이다.그래서 우 리 는 앞 순 서 를 이용 하여 먼저 뿌리 노드 를 방문 한 다음 에 뿌리 노드 의 왼쪽 아 이 를 방문 합 니 다.이때 우리 의 현재 노드 는 왼쪽 아이 이 고 처음에 뿌리 노드 에 접근 할 수 없 기 때문에 하나의 스 택 으로 저장 하고 뒤로 물 러 나 기 편리 해 야 합 니 다.여기 서 내 가 선택 한 것 은 ArrayList onePath = new ArrayList(); 을 저장 소 로 하 는 것 이다.우리 가 잎 노드 를 방 문 했 을 때 모든 노드 의 값 은 target 과 같 지 않 고 오래 전에 이전 노드 로 되 돌아 가 그의 하위 노드 를 방문 합 니 다.
종합 적 으로 분석 하면 코드 는 다음 과 같다.
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 {
    //          ArrayList
    ArrayList> allPath = new ArrayList>();
    ArrayList onePath = new ArrayList();

    public ArrayList> FindPath(TreeNode root,int target) {
        if(root == null)
            return allPath;

        onePath.add(root.val);
        target = target - root.val;
        if(target == 0 && root.left == null && root.right == null){
            allPath.add(new ArrayList(onePath));
        }

        FindPath(root.left,target);
        FindPath(root.right,target);

        onePath.remove(onePath.size() - 1);


        return allPath;
    }
}
[C++] 백준 2606 : 바이러스
BOJ 15727

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage