[LeetCode]145. Binary Tree Postorder Traversal

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */

import java.util.*;
class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> output = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        TreeNode visited = null;
        while (root!=null || !stack.empty()){
            if (root!=null){
                stack.push(root);
                root = root.left;
            }else {
                TreeNode prev = stack.peek();
                if (prev.right != null && visited != prev.right){
                    root = prev.right;
                }else {
                    visited = stack.pop();
                    output.add(visited.val);
                }
            }
        }
        return output;
    }
    private void print(TreeNode node){
        if (node != null)
            System.out.println(node.val);
    }
}

이진 트리 순회

전위 순회 (Preorder Traversal): "루트 - 왼쪽 - 오른쪽"
중위 순회 (Inorder Traversal): "왼쪽 - 루트 - 오른쪽"
후위 순회 (Postorder Traversal): "왼쪽 - 오른쪽 - 루트"

이진 트리 후위 순회에서 lastVisited 변수의 중요성

이진 트리의 후위 순회는 왼쪽 서브트리, 오른쪽 서브트리, 그리고 루트 노드 순으로 방문하는 순회 방식입니다.
재귀적 방법으로 구현할 때는 이 순서를 쉽게 지킬 수 있지만, 반복적(iterative) 방법으로 구현할 때는 약간의 트릭이 필요합니다.
여기서 lastVisited 변수가 중요한 역할을 합니다.

lastVisited 변수의 역할

• 오른쪽 자식 노드 방문 여부 확인: lastVisited 변수는 직전에 방문한 노드를 추적하여, 현재 노드의 오른쪽 자식을 이미 방문했는지 확인하는 데 사용됩니다.
• 불필요한 반복 방지: 스택의 top에 있는 노드를 처리해야 할지, 아니면 오른쪽 자식으로 이동해야 할지 결정할 때 lastVisited를 사용합니다.

if (prev.right != null && lastVisited != prev.right){
    cur = prev.right;
}
else {
    output.add(prev.val);
    lastVisited = stack.pop();
}

이 부분에서 lastVisited의 역할이 명확히 드러납니다:
prev.right != null && lastVisited != prev.right 조건은 오른쪽 자식이 있고,
그 자식이 마지막으로 방문한 노드가 아닌 경우를 확인합니다.

이 조건이 참이면, 오른쪽 자식으로 이동합니다 (cur = prev.right).

조건이 거짓이면, 현재 노드를 처리하고 (output.add(prev.val)), 스택에서 제거한 후 (stack.pop()), 이를 lastVisited로 설정합니다.

lastVisited 없이는 어떤 문제가 발생할까?

• 무한 루프: 오른쪽 자식 노드로 계속 이동하다가 다시 부모 노드로 돌아오는 과정에서 무한 루프에 빠질 수 있습니다.
• 잘못된 순서: 노드 처리 순서가 올바르지 않아 후위 순회의 정의를 위반할 수 있습니다.

결론

lastVisited 변수는 이진 트리의 반복적 후위 순회 알고리즘에서 핵심적인 역할을 합니다.
이 변수를 통해 알고리즘은 현재 노드의 처리 시점을 정확히 결정할 수 있으며,
이는 후위 순회의 "왼쪽 - 오른쪽 - 루트" 순서를 올바르게 유지하는 데 필수적입니다.
트리 순회 알고리즘을 구현할 때 이러한 세부사항에 주의를 기울이면, 더 효율적이고 정확한 코드를 작성할 수 있습니다.