검지 Offer - 두 갈래 트리 중 하나에 해당하는 경로

제목 설명

두 갈래 나무의 노드와 정수를 입력하고 두 갈래 나무의 결점 값과 정수를 입력하는 모든 경로를 출력합니다.경로는 나무의 뿌리 결점에서 시작하여 잎 결점까지 내려가는 결점으로 경로를 형성합니다.(주의: 값을 되돌려주는list에서 그룹 길이가 큰 그룹이 앞에 있습니다)
문제 풀이 사고방식을 간소화하다: 이 문제는 차례대로 사용하는 것을 추천합니다!경로를 형성하려면 깊이 우선 검색을 사용하고 대기열에 노드를 추가한 후에 target 값이 만족스러운지 판단하고 만족하지 않으면 계속 좌우 트리로 돌아가고 어떤 잎 노드로 돌아가면 현재 노드의 값이 target에 만족하지 않으면 대기열이 현재 노드로 되돌아가야 한다.만약 제목에 주의사항을 요구하지 않는다면, 이 코드는 완벽하다고 할 수 있다.(테스트 용례가 너무 적어서 코드는 AC가 가능합니다.)그러나 마지막으로 되돌아오는 리스트에서 그룹 길이가 큰 그룹이 앞에 있는 것을 무시했다.만약 판단 수조의 길이를 더하려면 귀속을 주 함수에 쓸 수 없으며, 분리해야 한다.최적: 그룹 길이 정렬, Collections를 사용할 수 있습니다.sort 방법, Collections는 도구 클래스입니다. sort는 그 중의 정적 방법으로 List 형식을 정렬하는 데 사용됩니다.그러나 기본값은 정렬입니다. 역순을 실현하려면Comparator 인터페이스의compare 방법을 다시 써서 사용자 정의 정렬을 완성해야 합니다.
주:compare가 되돌려주는 int 값은 세 가지 종류가 있습니다.compare(대상 1, 대상 2) 마이너스 정수: 대상 1이 상위 0: 위치가 변하지 않는 정수: 대상 1이 뒤에 있습니다

Java 씬 퀴즈

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 {
    private ArrayList> result = new ArrayList<>();
    private ArrayList list = new ArrayList<>();
    public ArrayList> FindPath(TreeNode root,int target) {
        if(root==null || root.val>target)
            return result;
        list.add(root.val);
        target -=root.val;
        if(target==0 && root.left==null && root.right==null)
            result.add(new ArrayList(list));
        if(root.left!=null) FindPath(root.left, target);
        if(root.right!=null) FindPath(root.right, target);
        list.remove(list.size()-1);
        return result;
    }
}

최적 상태 - 배열 정렬 포함

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
public class Solution {
    private ArrayList> result = new ArrayList<>();
    private ArrayList list = new ArrayList<>();
    public ArrayList> FindPath(TreeNode root,int target) {
        GetPath(root, target);
        Collections.sort(result, new Comparator>() {
            @Override
            public int compare(ArrayList o1, ArrayList o2) {
                if(o1.size()target)
            return;
        list.add(root.val);
        target -=root.val;
        if(target==0 && root.left==null && root.right==null)
            result.add(new ArrayList(list));
        if(root.left!=null) GetPath(root.left, target);
        if(root.right!=null) GetPath(root.right, target);
        list.remove(list.size()-1);
    }
}