[LeetCode] 94. Binary Tree Inorder Traversal - 문제풀이

Description

주어진 이진트리를 중위순회(Inorder-traversal)하여 값을 반환하는 문제입니다.

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

Example 1:

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

Example 2:

Input: root = []
Output: []

Example 3:

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

Constraints:

• The number of nodes in the tree is in the range [0, 100].
• -100 <= Node.val <= 100

Follow up:

Recursive solution is trivial, could you do it iteratively?

Solution 1. 재귀호출 (Recursion)

public List<Integer> inorderTraversal(TreeNode root) {

    // 1. Recursion - inorder
    List<Integer> list = new ArrayList<>();
    inorderTraversal(root,list);
    return list;
}
private void inorderTraversal(TreeNode node,List<Integer> list){
    if(node == null) return;
    inorderTraversal(node.left,list);
    list.add(node.val);
    inorderTraversal(node.right,list);
}

재귀 호출을 통한 방법입니다. left > root > right 순으로 순회하며 결과를 기록합니다.

• 시간복잡도 : O(n)
• 공간복잡도 : O(n)

Solution 2. 반복 (Iteration)

public List<Integer> inorderTraversal2(TreeNode root) {

    // 2. Iteration - inorder
    List<Integer> list = new ArrayList<>();
    if(root == null){return list;}
    Stack<TreeNode> stack = new Stack<>();
    pushAllLeft(root, stack);
    while (!stack.isEmpty()) {
        TreeNode cur = stack.pop();
        list.add(cur.val);
        pushAllLeft(cur.right, stack);
    }
    return list;
}

public void pushAllLeft(TreeNode node, Stack stack){
    while (node != null) {
        stack.add(node);
        node = node.left;
    }
}

Stack과 반복문을 이용한 방법입니다. 알고리즘은 아래와 같습니다.

1. 더 이상 노드가 없을 때까지 루트의 모든 왼쪽 자식을 스택으로 푸시합니다.
2. 스택에서 마지막 왼쪽 노드를 pop(cur) 하여 결과에 추가
3. cur의 오른쪽 자식의 왼쪽 노드를 모두 스택에 넣어주는 것을 반복합니다.

Reference

Binary Tree Inorder Traversal - LeetCode