Binary Tree Level-Order Traversal: Using level as Index

First Thoughts

Recursion void helper method that adds the value of node to return array. Since void helper, called twice adter adding current node value, called with node.left and node.right if they are non-null. 문제점: 잘 더해졌지만 더해지는 순서가 꼬이는 현상이 발생했다..이게 in-order traversal이 아니라 level-order로 가야한다는 점을 주의하자. level order로 가려면 생각보다 left right으로 나누려면 너무 복잡하다 (지금 내가 생각나는 방법은 없다) 그래서 그냥 넘겨줄때 인자로 그 node level을 같이 넘겨주고 해당하는 list에 node value 추가하면 쉽게 끝날 문제이다.

Solution

public List<List<Integer>> levelOrder(TreeNode root) {
	List<List<Integer>> list = new ArrayList<List<Integer>>();
    if (root==null) return list;
    doWork(root, list, 0);
    return list;
}
public void doWork(TreeNode root, List<List<Integer>> list, int level) {
	if (root==null) return;
    if (level==list.size()) list.add(new ArrayList<Integer>())
    list.get(level).add(root.val);
    if (root.left!=null) doWork(root.left, list, level+1);
    if (root.right!=null) doWork(root.right, list, level+1);
}

Catch Point

1. Level 기준으로 순서대로 노드값을 더한다는건 in-order traversal과 같이 left, right 순서만 지키며 recurse한다고 되는 문제가 아니라, 해당 노드의 level을 같이 넘겨줘야한다.

2. 이때, 만약 해당 level이 처음 불려진 것이라면 새로운 arrayList를 만들어줘서 main list에 더해줘야한다. (왜냐면 그 subList level기준으로 get해서 더할거라서) 이때 조건을 level이랑 main list길이가 같다면 만들어주는 형식으로 해도된다 (처음 level을 0으로 잡아서 그렇다)

3. 중요한 포인트는 해당 level을 main list의 index로 활용했다는 것이다.