질문

이 기사에서는 Leetcode '144. Binary Tree Preorder Traversal' 질문을 다룰 것입니다. 이 질문은 쉬운 질문으로 평가됩니다.

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

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

질문 설명

질문 자체가 꽤 잘 설명되어 있습니다. 이진 트리에서 선주문 깊이 우선 검색을 수행해야 합니다. 새 노드를 방문할 때마다 root에 array 값을 추가할 것입니다.

이제 모든 이진 트리 순회 알고리즘에 익숙하다면 이것은 사소한 문제입니다. 하지만 그렇지 않다면 이것에 대해 생각해야 합니다.

학습 깊이 우선 검색 및 모든 순회는 이진 트리 질문의 대부분에 대한 필수 지식입니다. 아래 순회를 마스터하는 것이 좋습니다.

깊이 우선 검색:

Pre-order

In-order

Post-order

리트코드 질문

Binary Tree Preorder Traversal

Binary Tree Inorder Traversal

Binary Tree Postorder Traversal

권장 지식

Binary Tree

Depth First Search

Recursion

Call Stack

어떻게 할 것인가:

이 질문의 핵심은 깊이 우선 검색 알고리즘을 이해하는 것입니다. 루트에서 시작하여 가장 왼쪽node에서 가장 오른쪽node으로 이동하여 모든 nodes가 만료될 때까지 모든 사람을 방문하는 방법입니다. 각 지점에서 nodes 값을 list 에 추가합니다.

우리는 이것을 재귀적으로 할 것입니다.

함수 매개변수 내에서 list 변수를 선언합니다. 기본적으로 빈 배열이 됩니다.

먼저 '주어진 노드가 비어 있습니까?'라고 묻습니다. 그렇다면 지금까지 가지고 있는 목록을 반환합니다. 그렇지 않은 경우 node 값을 list에 추가한 다음 left 및 right 노드에서 함수를 재귀적으로 호출합니다.

nodes를 모두 소진할 때까지 위의 알고리즘을 반복합니다.

함수 끝에 list가 반환됩니다.

빅오 표기법:

시간 복잡도: O(n) | 여기서 n은 트리에 있는 노드 수 | 우리는 항상 전체 트리를 탐색하므로

공간 복잡도: O(h) | 호출 스택을 사용하여 노드를 저장하므로

리트코드 결과:

제출 링크 참조:

런타임: 이진 트리 사전 주문 순회

에 대한 JavaScript 온라인 제출의 91.84%보다 59ms 빠름

메모리 사용량: 42.2MB, Binary Tree Preorder Traversal에 대한 JavaScript 온라인 제출의 63.12% 미만

해결책

var preorderTraversal = function (root, list = []) {

    /* -------------------------------------------------------------------------- */
    /*                     144. Binary Tree Preorder Traversal                    */
    /* -------------------------------------------------------------------------- */

    /**
     * @author  Samuel Hinchliffe
     * @see    {@link linkedin.com/in/samuel-hinchliffe-🚀-2bb5801a5/ | Author's Linkedin }
     * @see    {@link github.com/Samuel-Hinchliffe}
     */

    // We're at a empty node, so we return our list here
    // Just in case the list is empty, we return an empty list
    if (!root) {
        return list;
    }

    // We're at a non-empty node, so we add the value to our list
    // We're doing this in a preorder manner. 
    list.push(root.val);

    // Traverse to the left node and right nodes
    preorderTraversal(root.left, list);
    preorderTraversal(root.right, list);

    // We traversed this entire little tree
    // So let's return our list. 
    return list;
};