[LeetCode/JAVA] 589. N-ary Tree Preorder Traversal

 

 

https://github.com/ROUTINE-STUDY/Algorithm

알고리즘 스터디를 진행하고 있습니다.
초보들로 구성되어있으며, 열심히 풀어보고 풀이 방식을 공유하고 피드백을 해주는 스터디입니다.
참여 문의는 댓글 혹은 GitHub 주소를 참고해주세요.

---

문제 출처 : https://leetcode.com/problems/n-ary-tree-preorder-traversal/

 

출처 : LeetCode

문제 설명

주어진 트리를 예제와 같이 탐색하는 트리를 반환하세요.
즉, 깊이우선탐색(DFS)으로 해당 노드를 탐색하면 됩니다.

풀이 방법

기본 DFS 구현 로직 중 재귀를 활용하여 풀이하였습니다.

내 코드(JAVA)

 

public class Solution {

    // return 객체 인스턴스 변수로 생성
    public List<Integer> res = new ArrayList<>();

    // dfs 재귀를 이용하여 구현
    public List<Integer> preorder(Node root) {
        dfs(root);
        return res;
    }

    // 기존 DFS는 방문 노드를 체크하는 로직이 들어가지만,
    // 위 문제에서는 같은 값의 노드가 존재하고 탐색 순서만 묻는 문제이므로, 방문여부 체크로직 삭제
    public void dfs(Node root) {
        if(root == null) return;

        res.add(root.val);

        for(Node node : root.children) {
            dfs(node);
        }
    }
    
}

 

다른 사람 코드

 

class Solution {
    public List<Integer> list = new ArrayList<>();
    public List<Integer> preorder(Node root) {
        if (root == null)
            return list;
        
        list.add(root.val);
        for(Node node: root.children)
            preorder(node);
                
        return list;
    }
}

 

메서드를 새로 만들지 않아도 구현이 가능했습니다..

DFS 문제를 좀 더 많이 풀어봐야 할 것 같습니다.

 

class Solution {
    public List<Integer> preorder(Node root) {
        List<Integer> list = new ArrayList<>();
        if (root == null) return list;
        
        Stack<Node> stack = new Stack<>();
        stack.add(root);
        
        while (!stack.empty()) {
            root = stack.pop();
            list.add(root.val);
            for (int i = root.children.size() - 1; i >= 0; i--)
                stack.add(root.children.get(i));
        }
        
        return list;
    }
}

 

Stack을 활용한 풀이입니다.

좌측부터 탐색하고 Stack을 활용하기 때문에 node의 children들을 오른쪽(끝)부터 넣어

맨 좌측 자식 노드가 최상단으로 올라오게 하는 것이 핵심인 것 같습니다. 

 

DFS 문제 풀이 시 Stack 및 재귀를 모두 활용한 풀이를 도전해봐야겠습니다.

 

 

다른 사람 코드 출처