leetcode 144, Binary Tree Preorder Traversal

문제 설명

이진 트리가 주어졌을 때 전위 순회의 순서를 구해서 리스트에 넣어 반환하는 문제다.

순회

1. 전위 순회(preorder traverse)
   부모 노드 -> 왼쪽 자식 노드 -> 오른쪽 자식 노드
2. 중위 순회(inorder traverse)
   왼쪽 자식 노드 -> 부모 노드 -> 오른쪽 자식 노드
3. 후위 순회(postorder traverse)
   왼쪽 자식 노드 -> 오른쪽 자식 노드 -> 부모 노드

코드 설명

0. 변수
   0-1. answer, 정답인 노드를 저장하는 변수
1. 만일 주어진 root가 null이라면 아무것도 안 들어가 있는 answer을 반환한다. root에 값이 있다면 전위 순회를 한다.
2. 전위 순회는 만일 현재 노드가 값이 null이라면 해당 메소드를 끝낸다. 아니라면 현재 노드의 val을 answer에 넣고 현재 노드의 왼쪽 자식 노드를 탐색하고 그 다음 오른쪽 노드를 탐색한다.

코드

class Solution {
    public static List<Integer> answer;
    public List<Integer> preorderTraversal(TreeNode root) {
        answer = new ArrayList<>();

        if(root == null){
            return answer;
        }

        dfs(root);

        return answer;

    }

    public static void dfs(TreeNode node){
        if(node == null){
            return;
        }

        answer.add(node.val);
     
        dfs(node.left);
        dfs(node.right);

    }
}

링크

https://leetcode.com/problems/binary-tree-preorder-traversal/description/