[LeetCode] 94. Binary Tree Inorder Traversal #Easy #Java

문제
Given the root of a binary tree, return the inorder traversal of its nodes' values.

예제 1

Input: root = [1,null,2,3]
Output: [1,3,2]

예제 2

Input: root = [1,2,3,4,5,null,8,null,null,6,7,9]
Output: [4,2,6,5,7,1,3,9,8]

예제 3

Input: root = []
Output: []

예제 4

Input: root = [1]
Output: [1]

제약조건
✅ The number of nodes in the tree is in the range [0, 100]. 
✅ -100 <= Node.val <= 100

 

문제풀이

/**
 * 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;
 *     }
 * }
 */
class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        // 1. 변수 선언 및 초기화
        List<Integer> result = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        TreeNode currentNode = root;

        // 2. 주어진 노드가 모두 소요되거나 스택이 비었을 경우 종료
        while (currentNode != null || !stack.isEmpty()) {
            // 왼쪽 노드로 이동
            while (currentNode != null) { 
                stack.push(currentNode);
                currentNode = currentNode.left;
            }
            
            // 스택 제일 위에 있는 노드 결과에 추가
            currentNode = stack.pop();
            result.add(currentNode.val);

            // 오른쪽 노드로 이동
            currentNode = currentNode.right;
        }

        // 3. 반환
        return result; 
    }
}

• 주어진 트리를 중위 순회하는 문제이다.

 

• 가령 예제 2는 4 - 2 - 6 - 5 - 7 - 1 - 3 - 9 - 8 순서로 트리를 순회하는 것이다.

트리를 이해하는 것과 구현하는 것은 확실히 차이가 있는 것 같다. 🙄

 

• 굳이 최적화를 하자면 currentNode != null || !stack.isEmpty() 조건의 순서를 바꾸는 것이다.
• if문은 단락 평가를 하므로 왼쪽 조건이 true면 오른쪽 조건은 검사를 하지 않는다.
• stack은 반복문을 도는 동안 비어있는 순간이 없다.
• 반면 currentNode는 왼쪽 노드 끝으로 이동했을 때마다 null이 되므로 조건을 2개 검사하는 순간이 종종 발생한다.
• 그런데 사실 분기가 엄청 많은 트리가 아니고서야 큰 의미는 없다.

그래도 단락 평가는 코딩할 때 고민해야 할 요소 중 하나인 건 틀림 없다.

 

이미지 출처

[김은우의 에듀테크 트렌드 따라잡기] 코딩 교육 사이트 LeetCode가 보여주는 코딩교육의 핵심