[LeetCode] 144. Binary Tree Preorder Traversal - 문제풀이

Description

전위 순회(preorder-traversal)하며 값을 읽어 List에 순서대로 넣어 반환하는 문제입니다.

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

Example 1:

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

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> preorderTraversal(TreeNode root) {
    List<Integer> list = new ArrayList<>();
    preorderTraversal(root,list);
    return list;
}

private void preorderTraversal(TreeNode node,List<Integer> list){
    if(node == null) return;
    list.add(node.val);
    preorderTraversal(node.left,list);
    preorderTraversal(node.right,list);
}

깊이우선탐색(DFS)과 유사하게 재귀호출을 통해 root > left > right 순으로 전위 순회(preorder-traversal)하며 값을 채워 넣습니다.

Solution 2. 반복(Iteration)

public List<Integer> preorderTraversal(TreeNode root) {

        // 2. iteration  - preorder
        List<Integer> list = new ArrayList<>();

        if(root == null){return list;}
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while(!stack.isEmpty()){
            TreeNode node = stack.pop();
            list.add(node.val);
            if(node.right != null) stack.push(node.right);
            if(node.left != null) stack.push(node.left);
        }
        return list;
    }

재귀호출없이 stack과 반복문을 이용한 방법입니다. root를 탐색하고 나중에 탐색해야 하는 right노드를 먼저 stack에 넣고 left를 나중에 넣어 먼저 탐색 될 수 있도록 반복합니다. 결과적으로 root > left > right순으로 전체 스캔하게 됩니다.

Reference

Binary Tree Preorder Traversal - LeetCode