LeetCode 145(Binary Tree Postorder Traversal, java)

0. 문제

https://leetcode.com/problems/binary-tree-postorder-traversal/

Binary Tree Postorder Traversal - LeetCode

 

1. 문제 설명

- 문제에서 이진트리(root)가 주어진다.

- 해당 이진트리를 후위 순회 방식으로 탐색하여, 탐색한 순서대로 노드의 값을 배열에 담아 반환하는 것이 핵심이다.

 

2. 문제 해설

a) 첫 번째 접근

- 후위 순회는 좌측 자식 노드 - 우측 자식 노드 - 부모 노드 순서로 탐색한다.

- 이 방식을 재귀 함수로 구현하면 된다. 

 

b) 두 번째 접근

- 우선 좌측 자식 노드를 계속해서 탐색한다.

- 가장 좌측에 위치한 단말 노드 A를 만나게 되면, 좌측 노드에 대한 탐색을 중단한다.

- 그리고 이전 노드(= 단말 노드 A)로 돌아가 우측 자식 노드를 탐색한다.

- 그러나 해당 노드는 단말 노드이므로 더 이상 자식 노드가 존재하지 않는다.

- 그러므로 우측 자식 노드의 탐색 또한 종료하고 이전 노드(= 단말 노드 A)로 돌아간다.

- 단말 노드 A의 값을 배열에 저장한다. 

 

- 위의 예시를 통해 단말 노드 A는 어떤 상위 노드(= 부모 노드)의 좌측 자식 노드일 수 있다.

- 또는 단말 노드 A가 어떤 상위 노드 그 자체일 수 있다.

 

- 매번 재귀가 반복할 때마다 좌측 자식 노드를 우선적으로 탐색하기 때문이다.  

- 그러므로 단말 노드 A가 더 이상 좌/우측 자식이 없다는 것을 확인한 후 배열에 저장한다.

 

- 이 과정을 재귀 함수로 그대로 구현하면 된다. 

- 다음 코드를 보면서 이해해보자. 

 

3. 정답 코드

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