[두 번 지나침] LeetCode257: 두 갈래 나무의 모든 경로

* 두 갈래 나무를 지정하여 뿌리 노드에서 잎 노드까지의 모든 경로를 되돌려줍니다.
*설명: 잎 노드는 하위 노드가 없는 노드를 말합니다.
* 예:
* 입력:
 * ⁠  1
 * ⁠/   \
 * 2     3
 * ⁠\
 * ⁠ 5
* 출력: ["1->2->5", "1->3"]
* 설명: 모든 루트 노드에서 잎 노드까지의 경로: 1->2->5, 1->3

문제 해결 방법:


직접 폭력 DFS.
매번 노선을 되돌려야 하기 때문에, 길을 따라 지나간 노드를 저장하기 위해 추가path 집합을 유지해야 합니다.지나가는 노드를 검색할 때마다path 집합에 잃어버리고 잎 노드를 만났을 때까지 이 경로를 표시하여 결과 집합에 저장합니다.
주의해야 할 것은 한 길을 수색한 후 다른 노선을 수색할 때 현장을 거슬러 올라가야 한다는 것이다.
class Solution {
    private List res = new ArrayList<>();
    private List path = new ArrayList<>();

    public List binaryTreePaths(TreeNode root) {
        dfs(root);

        return res;
    }

    private void dfs(TreeNode root){
        if(root == null)
            return;
        
        path.add(root.val);
        if(root.left == null && root.right == null){
            res.add(collection2String(path));
        }

        dfs(root.left);
        dfs(root.right);
        path.remove(path.size()-1);
    }

    String collection2String(List path){
        StringBuilder sb = new StringBuilder();

        for(int i=0; i");
            }
        }

        return sb.toString();
    }
}

좋은 웹페이지 즐겨찾기