트리 순회, N-ary Tree Preorder Traversal

Problem

589. N-ary Tree Preorder Traversal

Given the root of an n-ary tree, return the preorder traversal of its nodes’ values.

Nary-Tree input serialization is represented in their level order traversal. Each group of children is separated by the null value (See examples)

문제 해석

Preorder: self left right (나 자신을 먼저 순회)

이전의 Inorder traverse문제는 left, right 포인터를 가지고 있었지만 이번에는 주어진 list에 들어있는 null을 기준으로 트리의 layer level을 구분한다

My Approach

시도

주어진 Input리스트를 순회하면서 null값이 나올때마다 레이어를 구분하고 처음 나오는 node를 ret리스트에 담는다

문제: 자식 노드가 몇개씩 있는지 모르기 때문에 해당 접근법은 틀림

아래의 두 가지 방법으로 해결 가능

1. Recursive Solution
2. Iterative Solution

Recursive Solution

/* Node class가 미리 정의 되어 있음
// Definition for a Node.
class Node {
    public int val;
    public List<Node> children;

    public Node() {}

    public Node(int _val) {
        val = _val;
    }

    public Node(int _val, List<Node> _children) {
        val = _val;
        children = _children;
    }
};
*/

class Solution{
    public List<Integer> preorder(Node root) {
        List<Integer> ret = new ArrayList<>();
        traverse(root, ret);
        return ret;
    }

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

Iterative solution

Stack에 루트노드를 담고 해당 노드를 꺼낼 때 마다 값을 결과 리스트에 담고 자식 노드들을 Stack에 담아준다. 가장 뒤의 자식순으로 담는것이 포인트!

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

	}
	return ret;
}