LeetCode-257- 두 갈래 나무의 모든 경로

두 갈래 나무의 모든 경로

제목 설명: 두 갈래 나무를 정해서 뿌리 노드에서 잎 노드까지의 모든 경로를 되돌려줍니다.
설명: 잎 노드는 하위 노드가 없는 노드를 가리킨다.
예시 설명은 LeetCode 홈페이지를 참조하십시오.
출처: 리코드(LeetCode) 링크:https://leetcode-cn.com/probl... 저작권은 인터넷 소유에 귀속된다.상업 전재는 정부에 연락하여 권한을 부여하고, 비상업 전재는 출처를 명시해 주십시오.
해법1: 귀속법

우선, 루트가null이면 빈 List로 바로 돌아갑니다..

주 방법의 처리 과정은 귀속 방법을 호출하는 것이다. 초기 경로 path는 루트의 노드 값이고 좌우 트리가 있는지 여부에 따라 귀속 방법의 매개 변수와 몇 번 호출하는 방법이다

귀속 방법은 2개의 매개 변수가 있는데 하나는 현재 노드 루트이고 하나는 현재 경로 path이며 귀속 과정은 다음과 같다.

루트가 비어 있으면 현재 path를result에 추가합니다.

루트의 좌우 트리가 비어 있으면path에 현재 노드의 값을 추가한 다음result에 추가하여 되돌려줍니다

만약에 루트의 왼쪽 트리가 비어 있다면 이 방법을 반복적으로 호출합니다. 매개 변수는 루트의 오른쪽 노드이고 path는path에 현재 노드의 값을 추가합니다

만약에 루트의 오른쪽 트리가 비어 있다면 이 방법을 반복적으로 호출합니다. 매개 변수는 루트의 왼쪽 노드이고 path는path에 현재 노드의 값을 추가합니다

만약에 루트의 좌우 트리가 비어 있지 않으면 2차 귀속 방법을 호출합니다. 매개 변수는 각각 루트의 좌우 노드이고 path는 path에 현재 노드의 값을 추가합니다

import java.util.ArrayList;
import java.util.List;

public class LeetCode_257 {
    private static List result = new ArrayList<>();

    public static List binaryTreePaths(TreeNode root) {
        if (root == null) {
            return new ArrayList<>();
        }
        if (root.left == null) {
            binaryTreePaths(root.right, root.val + "");
        } else if (root.right == null) {
            binaryTreePaths(root.left, root.val + "");
        } else {
            binaryTreePaths(root.right, root.val + "");
            binaryTreePaths(root.left, root.val + "");
        }
        return result;
    }

    private static void binaryTreePaths(TreeNode root, String path) {
        if (root == null) {
            result.add(path);
            return;
        }
        if (root.left == null && root.right == null) {
            path += "->" + root.val;
            result.add(path);
        } else {
            path += "->" + root.val;
            if (root.left == null) {
                binaryTreePaths(root.right, path);
            } else if (root.right == null) {
                binaryTreePaths(root.left, path);
            } else {
                binaryTreePaths(root.right, path);
                binaryTreePaths(root.left, path);
            }
        }
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.right = new TreeNode(5);

        for (String path : binaryTreePaths(root)) {
            System.out.println(path);
        }
    }
}

[일일 우송]
해가 우리를 저버리지 않았으니 우리도 절대로 해를 저버리지 마라.