Binary Tree Preorder Traversal (Stack)

LeetCode의 Binary Tree 튜토리얼을 시작하게 됐다. 그중 첫 번째 문제인 트리의 Pre-order 탐색을 구현하는 문제인 Binary Tree Preorder Traversal이다.

Explore - LeetCode

문제는 간단하다. 이전에 풀었던 Binary Tree Inorder Traversal (Stack)과 비슷하게 스택을 활용하여 Pre-order 탐색을 구현하는 것인데 다시 한번 정리하자면 이 탐색 방법은 다음과 같은 종류들이 있다.

• Pre-order: 루트, 왼쪽, 오른쪽 노드 순서대로 탐색.

• In-order: 왼쪽, 루트, 오른쪽 노드 순서대로 탐색.

• Post-order: 왼쪽, 오른쪽, 루트 노드 순서대로 탐색.

• 이 탐색들은 재귀 혹은 반복문을 통해 구현될 수 있음.

이전에도 언급했지만 Post-order는 (4 * (2 + 3)) 같은 표현식을 컴퓨터가 이해하는데 도움이 되는 탐색 방법이라는 특징이 있다. 위의 그림과 같은 표현식은 2 + 3을 나타낸 것인데 사람이 읽는 방법은 '2', '+', '3' 즉 왼쪽, 루트, 오른쪽 노드 순서대로 방문하는 In-order지만 컴퓨터는 '2', '3', '+' 즉 왼쪽, 오른쪽, 루트 노드 순서대로 방문하는 Post-order인 것이다.

 

아무튼 Pre-order 탐색을 구현하려면 루트 노드 탐색 후 왼쪽 서브 트리, 오른쪽 서브 트리를 탐색해야 하기 때문에 스택에 오른쪽, 왼쪽 노드 순서대로 삽입한 후 왼쪽 노드를 꺼내서 다시 탐색하는 방법을 생각해볼 수 있다. 그리고 이전 In-order와는 다르게 왼쪽 서브 트리의 끝까지 파고들어가서 탐색을 시작하는 게 아니라 루트 노드가 최우선이기 때문에 매 탐색마다 해당 노드를 탐색(노드의 값을 결과 배열에 추가) 해야 한다. 이를 기반으로 작성한 코드는 다음과 같다.

import java.util.Stack;
import java.util.LinkedList;


class Solution {
    Stack<TreeNode> stack = new Stack<>();
    LinkedList<Integer> result = new LinkedList<>();
    public List<Integer> preorderTraversal(TreeNode root) {
        if(root == null) return result;
        
        stack.push(root);
        while(stack.size() > 0){
            TreeNode node = stack.pop();
            result.add(node.val);
            
            if(node.right != null){
                stack.push(node.right);
            }
            if(node.left != null){
                stack.push(node.left);                
            }
            
        }
        
        return result;
    }
}

이전에 풀었던 In-order보다는 사용하는 자료구조가 좀 더 간단한 것을 볼 수 있다. 한쪽으로 먼저 파고든 후에 나오면서 탐색하는 과정이 아니라서 그런 것 같다.