Binary Tree Postorder Traversal (Stack)

LeetCode의 Binary Tree 튜토리얼 첫 번째 섹션의 네 번째 문제인 Binary Tree Postorder Traversal다.

In-order, Pre-order와 다르게 오늘따라 집중이 더 잘 안돼서 그런가 몇 시간을 허비한 것 같다. 안 되겠어서 그냥 풀이를 찾아봤는데 재귀적인 방식으로 하면 간단하지만 이전처럼 스택을 활용해서 푸는 방법은 없을지 고민하고 찾아보다가 시간을 너무 낭비한 것 같다.

 

알고리즘은 이곳에서 참고했다. 하나의 스택과 두 개의 노드 포인터를 사용하는데 노드 포인터는 각각 현재 탐색하는 노드, 이전에 탐색했던 노드를 가리키고 있으며 좀 특이하게 두 노드 포인터의 상하 관계(부모, 자식 노드)가 자주 바뀌기 때문에 이해하기가 좀 어려웠던 것 같다.

Iterative Postorder Traversal | Set 2 (Using One Stack) - GeeksforGeeks

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


class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {        
        Stack<TreeNode> stack = new Stack<>();
        LinkedList<Integer> result = new LinkedList<>();
        TreeNode current = null;
        TreeNode previous = null;

        if(root == null) return result;
        
        stack.push(root);
        while(!stack.empty()){
            current = stack.peek();
            
            // 조건 1 - 현재 노드가 이전 노드의 자식 노드
            if(previous == null || previous.left == current || previous.right == current){
                if(current.left != null){
                    stack.push(current.left);
                } 
                else if(current.right != null){
                    stack.push(current.right);
                } 
                else {
                    result.add(stack.pop().val);
                }
            // 조건 2  - 이전 노드가 현재 노드의 왼쪽 자식 노드
            } else if(current.left == previous){
                if(current.right != null){
                    stack.push(current.right);
                } else {
                    result.add(stack.pop().val);
                }
            // 조건 3  - 이전 노드가 현재 노드의 오른쪽 자식 노드
            } else if(current.right == previous){
                result.add(stack.pop().val);
            }
            
            previous = current;
        }
        
        return result;
    }
}

이번 코드는 보면서도 잘 이해가 안 되기 때문에 이론적인 부분은 제외하고 실제 코드를 기준으로 설명해보겠다. 먼저 알고리즘의 핵심은 다음과 같다.

• 현재 노드(current)는 루트 노드부터 시작한다. 이전 노드(previous)는 null 값으로 시작한다.

• 먼저 현재 노드가 이전 노드의 자식 노드 또는 처음 시작한 루트 노드(이전 노드가 null)인 경우 다음과 같다.

  • 현재 노드의 왼쪽 노드가 존재할 경우 왼쪽 노드를 스택에 삽입한다.

  • 그렇지 않고 오른쪽 노드가 존재할 경우 오른쪽 노드를 스택에 삽입한다.

  • 왼쪽, 오른쪽 노드가 둘 다 존재하지 않는다면 말단 노드기 때문에 결과 배열에 삽입한다.

• 반대로 이전 노드가 현재 노드의 자식 노드인 경우 다음과 같다.

  • 이전 노드가 현재 노드의 자식 노드라는 것은 말단 노드를 처리하고 돌아온 것이다.

  • 그렇기 때문에 이전 노드가 현재 노드의 왼쪽 자식 노드인 경우 현재 노드의 오른쪽 자식 노드가 존재하는지 확인하여 이를 스택에 삽입한다. 이전에 왼쪽 자식 노드를 탐색하고 돌아왔기 때문에 오른쪽 자식 노드를 탐색하는 것이다.

  • 반대로 이전 노드가 현재 노드의 오른쪽 자식 노드인 경우 왼쪽 노드와 오른쪽 자식 노드를 모두 처리하고 돌아온 것이기 때문에 현재 노드를 결과 배열에 삽입한다.

  • Post-order의 순서인 왼쪽, 오른쪽, 루트 노드를 순서대로 탐색할 수 있다.

• 매 탐색의 시작마다 현재 노드는 스택에 삽입된 가장 최근의 노드를 가리키고 탐색의 끝마다 이전 노드는 현재 노드를 가리킨다.

• 그렇기 때문에 추가적으로 서브 트리를 탐색하는 경우 스택에 노드가 삽입되기 때문에 현재 노드는 하위의 노드를, 이전 노드는 현재 노드의 부모 노드를 가리키게 된다.

• 추가적으로 탐색하지 않고 현재 노드를 결과 배열에 삽입하는 경우 스택에서 노드가 제거되기 때문에 현재 노드는 부모 노드를 가리키지만 이전 노드는 현재 노드(하위 노드)를 가리키게 된다.

잘 이해가 안 갈 수 있으니 과정을 그림으로 보이면 다음과 같다.

먼저 루트 노드부터 시작한다. 현재 노드는 1이고 이전 노드는 처음이기 때문에 아직 null이다. 시작 시 스택에 루트 노드를 삽입하고 시작하기 때문에 현재 스택에는 노드 1이 들어있다. 그리고 노드 1에 왼쪽 자식 노드가 존재하기 때문에 조건 1에 따라 이를 스택에 추가한다. 마지막으로 이전 노드를 현재 노드로 설정한 후 다음 탐색으로 넘어간다.

매 탐색의 시작에서는 스택에서 가장 최근에 삽입된 값(peek 메서드)을 현재 노드로 대입한다. 그래서 현재 노드는 노드 2를 가리키며 이전 노드는 노드 1을 가리키게 된다. 이 경우에도 조건 1(현재 노드가 이전 노드의 왼쪽 또는 오른쪽 자식)에 의해 노드 2의 왼쪽 자식 노드인 노드 4를 스택에 삽입하게 된다.

드디어 단말 노드까지 도달했다. 그런데 이 경우 현재 노드가 조건 1 중에서도 맨 마지막 조건, 즉 왼쪽 자식 노드와 오른쪽 자식 노드가 둘 다 존재하지 않는 경우에 해당한다. 그렇기 때문에 현재 노드의 값을 결과 배열에 삽입하고 스택에서 제거한다. 그러나 이전 노드는 별다른 조작 없이 현재 노드(노드 4)를 가리킨다.

이제 그다음이 까다로운 부분이다. 매 탐색의 마지막마다 이전 노드는 현재 노드를 가리키기 때문에 노드 4를 가리키게 되지만 이전 탐색에서 조건 1의 마지막 조건 때문에 스택에 있는 값을 꺼내서 결과 배열에 삽입하기만 했기 때문에 현재 탐색에서 현재 노드는 스택의 가장 최근 노드, 즉 노드 2를 가리키게 된다. 이 경우 이전까지 유지되던 현재 노드는 이전 노드의 자식 노드라는 관계가 역전된다. 이것이 조건 2, 조건 3에 해당한다.

 

Post-order에서는 위와 같은 상황에서 노드 4를 탐색한 후 노드 5, 노드 2를 탐색해야 한다. 그렇기 때문에 현재 노드가 노드 2이며 이전 노드가 노드 4일 경우 왼쪽 자식 노드를 탐색했기 때문에 오른쪽 자식 노드인 노드 5를 탐색해야 한다고 판단할 수 있다. 이것이 조건 2에 해당한다. 그리고 노드 2에서는 오른쪽 노드가 존재하기 때문에 이를 스택에 삽입하고 계속 탐색한다.

가장 최근에 스택에 삽입된 노드가 노드 2의 오른쪽 자식 노드인 노드 5기 때문에 현재 노드는 노드 5를 가리킨다. 그리고 이전 노드는 노드 2를 가리키고 있다. 이는 조건 1에 해당하며 노드 4 때와 마찬가지로 왼쪽 자식 노드와 오른쪽 자식 노드가 모두 존재하지 않으므로 현재 노드를 스택에서 삭제하여 결과 배열에 삽입하고 탐색을 계속한다.

노드 4 때와 마찬가지로 스택의 가장 최근 값인 노드 2가 현재 노드가 된다. 그리고 이전 노드는 현재 노드의 오른쪽 노드인데 이는 조건 3에 해당하기 때문에 이 노드의 모든 자식 노드를 탐색했다는 얘기가 된다. 왼쪽, 오른쪽, 루트 노드 순서대로 탐색하는 Post-order에서 왼쪽, 오른쪽 노드를 모두 탐색했으니 이제 루트 노드를 탐색해야 하며 이는 노드 2를 결과 배열에 삽입한다는 것을 의미한다. 그래서 조건 3에 의해 스택에서 현재 노드를 빼서 결과 배열에 삽입하고 끝내는 것이다.

 

결과적으로 Post-order에 맞게 노드 4, 노드 5, 노드 2 순서대로 탐색하게 되었다. 그러면 상위 노드에서는 어떻게 될까? 어쨌든 이진트리기 때문에 크게 보면 결국 하나의 서브 트리를 탐색하는 것과 동일하다.

시작 노드가 탐색의 처음과 동일하게 노드 1로 돌아왔다. 하지만 이번에는 이전 노드가 현재 노드의 왼쪽 자식 노드이며 조건 1이 아니라 조건 2에 해당한다. 그래서 현재 노드의 오른쪽 노드가 존재하기 때문에 이를 스택에 삽입하고 탐색을 진행한다.

노드 3은 어떤 자식 노드도 존재하지 않기 때문에 조건 1의 마지막 조건에 해당하여 스택에서 제거하고 결과 배열에 삽입된다.

그리고 다시 관계가 역전되어 조건 3에 해당된다. 이 경우 노드 1은 스택에서 제거되고 결과 배열에 삽입되며 스택에 아무런 노드도 남지 않아 탐색이 종료된다.

 

그래서 최종적으로 노드 4, 노드 5, 노드 2, 노드 3, 노드 1 순서대로 탐색하게 되며 이는 Post-order에 부합하는 방식이다.

 

다른 풀이를 찾아보니 두 개의 스택을 사용하여 거꾸로 탐색하는 방법도 있었다.

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        if (root == null) {
            return res;
        }
        Stack<TreeNode> first = new Stack<>();
        Stack<Integer> reverse = new Stack<>();
        first.add(root);
        while (!first.empty()) {
            TreeNode cur = first.pop();
            reverse.add(cur.val);
            if (cur.left != null) {
                first.add(cur.left);
            }
            if (cur.right != null) {
                first.add(cur.right);
            }
        }
        while (!reverse.empty()) {
            res.add(reverse.pop());
        }
        
        return res;
    }
}

Post-order 방식, 즉 왼쪽, 오른쪽, 루트 노드 순서대로 탐색하는 것을 반대로 해서 스택에 삽입하고 나중에 그 스택에 저장된 값을 꺼내서 탐색 결과를 뒤집어서 반환하는 로직이었는데 생각하기는 어려울 것 같지만 간단하게 구현할 수 있어서 인상 깊었다.

class Solution {
    List<Integer> list;
    public List<Integer> postorderTraversal(TreeNode root) {
        list=new ArrayList();
        fun(root);
        return list;
    }
    public void fun(TreeNode root){
       if(root==null)
           return;
       fun(root.left);
       fun(root.right);
       list.add(root.val);
    }
}

재귀 함수의 경우에는 허무할 정도로 간단한 방법이었다. 왼쪽, 오른쪽 노드를 재귀 탐색한 후 현재 노드를 결과 배열에 추가해주기만 하면 되는 방법이다.

 

 

예전에 In-order 탐색 문제에서는 하나의 노드 포인터만 유지하고 끝까지 파고 들어간 후에 나오면서 탐색하는 방식을 봐서 그런지 이번 문제에서도 비슷한 로직을 구현하려다가 실패했는데 생각해보니 예전에 학부 시절에 처음 배웠을 때는 재귀적인 방법을 사용했기 때문에 이번 문제를 푸는데 어려움이 좀 있었던 것 같다. 두 개의 노드 포인터와 그 관계를 바탕으로 현재 노드의 위치를 판단하는 방법은 생각지도 못했는데 공부가 많이 됐다.