.leetcode(589. N-ary Tree Preorder Traversal)

https://leetcode.com/problems/n-ary-tree-preorder-traversal/

 

1. 2022.01.09 시도

소요시간: 5분(1분 구상, 4분 코딩,recursive), 9분(iterative) 

// recursive
class Solution {
    public List<Integer> preorder(Node root) {
        List<Integer> output = new ArrayList<>();
        recursive(root, output);
        return output;
    }
    
    private void recursive(Node root, List<Integer> output) {
        if (root == null) {
            return;
        }
        
        output.add(root.val);
        for (Node child: root.children) {
            recursive(child, output);
        }        
    }
}

// iterative
class Solution {
    public List<Integer> preorder(Node root) {
        List<Integer> output = new ArrayList<>();
        if (root == null) {
            return output;
        }
        
        LinkedList<Node> stack = new LinkedList<>();
        stack.push(root);
        while(!stack.isEmpty()) {
            Node node = stack.pop();
            
            output.add(node.val);
            int length = node.children.size();
            for (int x=0; x<length; x++) {
                stack.push(node.children.get(length-x-1));
            }
        }
        
        
        return output;
    }
}

풀이 접근 과정

이런 traversal류는 recursive하고 iterative하게 풀이가 가능하다. 간단한 recursive부터 구현하였다. 결국 어디서 ouput.add를 해주냐가 관건인데 recursive는 일단 로직을 짜서 node를 순회하게 하고 add위치를 잡아주면 쉽다. 

iterative는 postorder, preorder등 마다 위치뿐만 아니라 넣는 순서도 중요하다. stack을 이용하기로 했으니 children을 넣을 때 꺼내기 좋게 역순으로 넣었다.

 

느낀점

• 순회자체는 몇번 풀어보면 공식이 보이니 어렵게 생각할 필요가 없다.

---

알고리즘 정리노트: .leetcode(알고리즘 문제풀이 접근)

반응형