LeetCode 144번 - Binary Tree Preorder Traversal

문제

주어진 이진 트리를 전위 순회하면서 노드 값을 리스트에 저장해 반환하는 문제이다.

---

살펴보기

전위 순회를 막 배운 시점에서 개념을 복습하기 좋은 문제같다!

 

전위 순회는

1. 현재 노드를 먼저 방문하고

2. 그 다음 왼쪽 자식 노드를 순회한 후

3. 마지막으로 오른쪽 자식 노드를 순회하는 방식이다.

---

풀어보기

노드값을 저장할 리스트를 선언한 후, 반환값이 void인 preorederTraversal 메서드를 호출해 리스트와 루트를 전달한다.

 

현재 노드가 null이면 return문을 통해 재귀 함수의 수행을 멈춘다.

null이 아닌 경우 리스트에 현재 노드의 값을 추가한 후,

왼쪽 자식 노드가 있으면 preorederTraversal 메서드를 다시 호출해 리스트와 왼쪽 자식 노드를 전달해 순회한다.

 

왼쪽 자식 노드의 순회가 끝나면 오른쪽 자식 노드를 똑같이 순회한다..

 

public List<Integer> preorderTraversal(TreeNode root) {
    List<Integer> nodeValueList = new ArrayList<>();

    if(root!=null){
        preorderTraversal(nodeValueList, root);
    }

    return nodeValueList;
}

public void preorderTraversal(List<Integer> nodeValueList, TreeNode root){
    if(root==null) return;

    nodeValueList.add(root.val);

    if(root.left!=null) preorderTraversal(nodeValueList, root.left);
    if(root.right!=null) preorderTraversal(nodeValueList, root.right);
}