기사 목록

1. 제목 묘사

2. 문제 풀이 사고방식

3. 문제 풀이 코드

4. 문제 풀이 소감

1. 제목 설명

  [JZ24]는 두 갈래 나무의 뿌리 노드와 정수를 입력하고 사전 순서에 따라 두 갈래 나무의 결점 값과 정수를 입력하는 모든 경로를 출력합니다.경로는 나무의 뿌리 결점에서 시작하여 잎 결점까지 내려가는 결점으로 경로를 형성합니다.지식점: 난이도:☆☆☆☆☆☆

2. 문제 풀이 방향

   두 갈래 나무의 범람은 두 가지가 있는데 그것이 바로 깊이 우선 DFS와 너비 유한 BFS이다. 전자는 귀속, 후자는 대기열을 사용하기에 적합하다.
   본제의 찾기 경로는 DFS에 속하기 때문에 귀속적인 해법을 써야 한다.
   귀속 함수의 기능:    입력 List, root, target.현재 결점root가 경로의 한 부분일 수 있는지 판단하고, 가능하다면list에 추가합니다.판단의 근거는 타겟. - 루트.val의 양과 음, 0보다 크면 현재 결점이 현재 경로의 일부분일 수 있음을 나타냅니다.  는 이어서 현재 결점root의 왼쪽 노드와 노드가 경로의 일부분일 수 있는지 차례로 판단한다.현재 결점 루트가 경로에 추가되면 target - root.val은 0이고 루트는 좌우 트리가 없습니다.하나의 경로가 발견되었다는 것을 알 수 있다.

3. 문제 풀이 코드

package pers.klb.jzoffer.hard;

import pers.klb.jzoffer.simple.TreeNode;

import java.util.ArrayList;

/**
 * @program: JzOffer2021
 * @description:  
 * @author: Meumax
 * @create: 2020-08-12 14:37
 **/
public class FindPath {
    private ArrayList<ArrayList<Integer>> lists = new ArrayList<>();

    public ArrayList<ArrayList<Integer>> FindPath(TreeNode root, int target) {
        if (root == null || root.val > target) return lists;
        dfs(root, target, new ArrayList<>());
        return lists;
    }

    public void dfs(TreeNode root, int target, ArrayList<Integer> list) {
        if (root == null) return;
        list.add(root.val);
        target -= root.val;
        if (target < 0) return;
        if (target == 0 && root.left == null && root.right == null)
            lists.add(new ArrayList<>(list));
        else {
            dfs(root.left, target, list);
            dfs(root.right, target, list);
        }
        list.remove(list.size() - 1);   //  ，  add  ， 
    }
}

4. 문제 풀이 소감

  DFS와 BFS를 능숙하게 파악하는 것이 두 갈래 나무를 두루 돌아다니는 문제를 해결하는 핵심이다.