Binary Tree

정의

트리의 각 노드 = 루트 값 + 자식 노드에 대한 참조 목록
이진 트리: 각 노드가 최대 두 개의 자식을 갖는 트리 자료 구조

순회

Pre-order Traversal

root -> left subtree -> right subtree (FBADCEGIH)

재귀

• 시간복잡도: O(N) (모든 노드를 한번씩만 방문)
• 공간복잡도: O(N) (최악의 경우 트리의 깊이 N)
  하지만 트리의 깊이가 너무 깊으면 Stack Overflow 발생할 수 있다.

private void preorderTraversal(TreeNode root, List<Integer> answer) {
	if (root == null) {
		return;
	}
	answer.add(root.val);                   // visit the root
	preorderTraversal(root.left, answer);   // traverse left subtree
	preorderTraversal(root.right, answer);  // traverse right subtree
}
public List<Integer> preorderTraversal(TreeNode root) {
	List<Integer> answer = new ArrayList<>();
	preorderTraversal(root, answer);
	return answer;
}

반복 (right node를 먼저 push 해야 left 부터 순회한다.)

• 시간복잡도: O(N)
• 공간복잡도: O(N)
  Stack Overflow 발생하지 않는다.

public List<Integer> preorderTraversal(TreeNode root) {
	List<Integer> answer = new ArrayList<>();
	Stack<TreeNode> s = new Stack<TreeNode>();
	if (root != null) {
		s.push(root);
	}
	TreeNode cur;
	while (!s.empty()) {
		cur = s.pop();
		answer.add(cur.val);            // visit the root
		if (cur.right != null) {
			s.push(cur.right);          // push right child to stack if it is not null
		}
		if (cur.left != null) {
			s.push(cur.left);           // push left child to stack if it is not null
		}
	}
	return answer;
}

In-order Traversal

left subtree -> root -> right subtree (ABCDEFGHI)

private void inorderTraversal(TreeNode root, List<Integer> answer) {
	if (root == null) {
		return;
	}
	inorderTraversal(root.left, answer);   // traverse left subtree
	answer.add(root.val);                  // visit the root
	inorderTraversal(root.right, answer);  // traverse right subtree
}
public List<Integer> inorderTraversal(TreeNode root) {
	List<Integer> answer = new ArrayList<>();
	inorderTraversal(root, answer);
	return answer;
}

Post-order Traversal

left subtree -> right subtree -> root (ACEDBHIGF)

트리에서 노드를 삭제할 때 post order 로 진행된다. 즉, 노드를 삭제하면 노드 자체를 삭제하기 전에 왼쪽 자식과 오른쪽 자식이 먼저 삭제된다.
또한 post order 는 수학 표현식에서 잘 사용된다. 스택을 이용하여 표현식을 쉽게 처리할 수 있다. 스택에서 두 요소를 꺼내 계산한 후, 그 결과를 다시 스택에 넣기만 하면 되기 때문이다.

private void postorderTraversal(TreeNode root, List<Integer> answer) {
	if (root == null) {
		return;
	}
	postorderTraversal(root.left, answer);   // traverse left subtree
	postorderTraversal(root.right, answer);  // traverse right subtree
	answer.add(root.val);                    // visit the root
}
public List<Integer> postorderTraversal(TreeNode root) {
	List<Integer> answer = new ArrayList<>();
	postorderTraversal(root, answer);
	return answer;
}

Level-order Traersal

1st level nodes -> 2nd level nodes -> 3rd level nodes -> ...

BFS는 트리나 그래프와 같은 자료 구조에서 탐색을 수행하는 알고리즘이다.

• 시간복잡도: O(N) (모든 노드가 한번씩만 큐에 들어간다)
• 공간복잡도: O(N) (가장 아래 레벨 노드의 개수만큼.. N/2)

Tree 문제 Solution

많은 트리 문제는 재귀로 해결 가능하다. 각 재귀 함수 호출에서 현재 노드의 문제에만 집중하고, 함수를 재귀적으로 호출하여 자식 노드 문제를 해결한다.

Top-Down

노드를 방문하여 값을 구하고, 함수를 재귀적으로 호출할 때 해당 값을 자식 노드에 전달한다. 따라서 Top-down 방식은 일종의 Preorder Traversal 로 볼 수 있다.

1. Null 노드에 대한 값 반환
2. 필요한 경우 ANSWER 업데이트
3. left_ans = top_down(root.left, left_params)
4. right_ans = top_down(root.right, right_params)
5. 필요한 경우 ANSWER 반환

예를 들어 최대 깊이를 구하는 문제에서, 자식 노드의 깊이는 (부모 노드 + 1)이다.

private int answer;

private void maximum_depth(TreeNode root, int depth) {
    if (root == null) {
        return;
    }
    if (root.left == null && root.right == null) {
        answer = Math.max(answer, depth);
    }
    maximum_depth(root.left, depth + 1);
    maximum_depth(root.right, depth + 1);
}

다음의 경우 Top-Down 방식을 고려할 수 있다.

• 각 노드가 답을 구하기 위해 매개변수가 필요한가?
• 매개변수와 노드 자체의 값으로 자식 노드에 전달해야 할 매개변수를 결정할 수 있는가?

Bottom-Up

먼저 모든 자식 노드에 대해 함수를 재귀적으로 호출한 다음, 반환된 값과 현재 노드 자체의 값에 따라 답을 구한다. 따라서 Bottom-up 방식은 일종의 Postorder Traversal 로 볼 수 있다.

1. Null 노드에 대한 값 반환
2. left_ans = bottom_up(root.left)
3. right_ans = bottom_up(root.right)
4. ANSWER 반환

예를 들어 최대 깊이를 구하는 문제에서, 노드의 깊이는 max(왼쪽 노드의 깊이, 오른쪽 노드의 깊이) + 1 이다.

public int maximum_depth(TreeNode root) {
    if (root == null) {
        return 0;                                   // return 0 for null node
    }
    int left_depth = maximum_depth(root.left);
    int right_depth = maximum_depth(root.right);
    return Math.max(left_depth, right_depth) + 1;   // return depth of the subtree rooted at root
}

다음의 경우 Bottom-Up 방식을 고려할 수 있다.

• 자식 노드의 답을 안다면 부모 노드의 답을 계산할 수 있는가?