.leetcode(590. N-ary Tree Postorder Traversal)

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

 

1. 2022.01.05 시도

소요시간: 9분(3분 구상, 6분 코딩, recursive), 17분(iterative)

// recursive
class Solution {
    public List<Integer> postorder(Node root) {
        List<Integer> ret = new ArrayList<>();
        if (root == null) {
            return ret;
        }
        
        recursive(root, ret);
        ret.add(root.val);

        return ret;
    }
    
    private void recursive(Node root, List<Integer> ret) {
        if (root == null) {
            return;
        }
        
        for(Node child: root.children) {
            recursive(child, ret);
            ret.add(child.val);
        }
    }
}

// iterative
class Solution {
    public List<Integer> postorder(Node root) {
        List<Integer> ret = new ArrayList<>();
        
        Stack<Node> stack = new Stack<>();
        stack.push(root);
        while(!stack.isEmpty()) {
            Node current = stack.pop();
            if (current == null) {
                continue;
            }

            ret.add(current.val);
            if (current.children == null) {
                continue;
            }
            
            for(int x=0; x<current.children.size(); x++) {
                stack.push(current.children.get(x));
            }
        }
        
        Collections.reverse(ret);
        return ret;
    }
}

풀이 접근 과정

recursvie하게 풀면 딱 좋겠다고 생각했다. 즉 재귀함수를 써야겠다고 마음먹었다. 시간복잡도 O(n)과 공간복잡도 O(n)이면 풀 수 있겠다 싶었다.

recursvie를 풀면서 iterative한 풀이를 생각했다. 보통 짝꿍처럼 recursive하게 풀 수 있는건 queue나 stack을 써서 iterative하게 풀 수 있다.

iterative하게 풀때 일단 pop을 해서 시작하는게 좋다. pop을 한 것을 어떻게 처리하면 좋지부터 생각해보는 것이다. postorder이다보니 뒤에서부터 접근해야되는데 이미 출력되는 root를 보니 이건 저장을 바로바로 해야겠다 싶었다. 저장하고나니 순서가 역순으로 될 것이 뻔했다. 몇가지 방법이 있는데 나는 Collections.reverse함수를 기억해서 그걸 쓰기로 했다. 다른 방법으로는 내가 저장한 ret의 리스트가 아닌 stack으로 받고 n번 돌면서 pop해서 list로 변환하는 방식이다.

 

느낀점

• recursive하게는 쉽게 풀렸는데 iterative생각하는게 되게 어색했다. 쉽게 푸는 방식이 있어도 스스로 질문을 던지고 그것에 맞는 코딩을 하고 그걸 해냈을 떄 성취감이 있다. 이번에 iterative는 내게 어색한 풀이방법이었는데 시간이 걸렸음에도 풀어서 조금은 친해진 느낌이다.
• 나같은 경우, Stack클래스를 사용하였는데 LinkedList로 써도 된다. pollLast메소드가 pop과 같은 효과이다.
• LinkedList<Integer> ret = new LinkedList<>(); 로 하면 addFirst메소드를 써서 reverse 정렬을 하거나 stack으로 받은 후 변환하거나 이런 일련의 과정을 하지 않아도 된다는걸 알았다.
• 조금 더 정리된 코드는 아래와 같다.

class Solution {
    public List<Integer> postorder(Node root) {
        LinkedList<Integer> ret = new LinkedList<>();
        if (root == null) {
            return ret;
        }
        
        Stack<Node> stack = new Stack<>();
        stack.push(root);
        while(!stack.isEmpty()) {
            Node current = stack.pop();
            ret.addFirst(current.val);
            
            for(Node child: current.children) {
                if (child == null) {
                    continue;
                }
                stack.push(child);
            }
        }
        return ret;
    }
}

---

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

반응형