솔루션 개발:

질문

이 기사에서는 Leetcode의 '114. Flatten Binary Tree to Linked List' 질문을 다룰 것입니다.

의문:

Given the root of a binary tree, flatten the tree into a "linked list":
The "linked list" should use the same TreeNode class where the right child pointer points to the next
node in the list and the left child pointer is always null.
The "linked list" should be in the same order as a pre-order traversal of the binary tree.

예시:

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

질문 설명

이 질문의 등급은 보통입니다. 정확하다고 생각합니다. O(n) 공간에서 이 질문을 알아내는 것은 매우 간단합니다. 선주문 순회를 수행하고 노드를 새 목록으로 보냅니다. 이 질문에 대해서는 트리를 내부에서 수정할 것입니다.

우리가 요청받은 것은 이진 트리를 연결된 목록으로 변환하고 연결 목록이 사전 순서로 순회하는 이진 트리처럼 보이도록 하는 것입니다.

이것은 처음에는 어렵게 보일 수 있지만 실제로는 매우 간단합니다. 아래 개념을 이해하는 한.

권장 지식

Binary Tree

Depth First Search

Post Order Traversal

Pre Order Traversal

Linked List

우리는 무엇을 알고 있습니까?

이진 트리가 있습니다(대부분 비어 있을 수 있음)

트리를 연결 목록으로 병합해야 합니다

.

O(h) 공간에 대해 이를 달성하려면 사후 순서로 트리를 탐색해야 합니다

.

왼쪽 트리를 현재 노드의 오른쪽 트리로 이동해야 합니다

.

어떻게 할 것인가:

우리는 사후 순회를 할 것입니다. 현재node의 전체 왼쪽 트리를 현재node의 오른쪽 트리로 옮기고 싶기 때문입니다. 왼쪽 트리의 끝이 현재right 노드를 가리킵니다. 혼란스럽게 들리겠지만 이해가 될 테니 걱정하지 마세요.

post_order_traversal를 사용하여 post order에 노드를 가져옵니다.

left 노드가 있는 노드를 찾을 때까지 사후 순서로 노드를 계속 순회합니다.

left node를 감지하면 lefts_right_most_node라는 새 포인터를 초기화합니다. 그의 임무는 root.left 더 오른쪽 노드를 찾는 것입니다. while 루프를 사용하여 right 노드를 찾을 때까지 계속 가져옵니다. 이렇게 하는 이유는 가장 오른쪽 노드가 해당 하위 트리의 맨 아래를 오른쪽 노드current에 연결하는 데 사용되기 때문입니다. 우리는 2개의 하위 트리를 하나로 병합할 것이기 때문에 이렇게 합니다.

lefts_right_most_node를 찾으면 lefts_right_most_node를 current 오른쪽 노드에 연결합니다.

그런 다음 current 노드의 오른쪽 노드를 lefts_right_most_node로 덮어씁니다. 이것은 왼쪽 트리의 마지막 노드가 현재 오른쪽 노드에 연결되기 때문에 작동합니다. 따라서 전체 왼쪽 트리를 오른쪽 트리에 삽입하지만 오른쪽 트리의 모든 요소 앞에 삽입합니다.

그런 다음 left 노드의 current 노드를 지웁니다. 이미 왼쪽 트리를 오른쪽 트리로 이동했기 때문에 더 이상 참조할 필요가 없습니다.

사후 순회가 끝날 때까지 이 작업을 계속 수행합니다.

빅오 표기법:

시간 복잡도: O(n) | 여기서 n은 이진 트리의 노드 수 | 트리 내의 모든 노드를 순회할 것입니다.

공간 복잡도: O(h) | 여기서 h는 호출 스택의 노드 높이 | 트리를 순회하기 위해 재귀 호출 스택을 사용하고 있기 때문입니다.

'이게 개선될 수 있을까?' 예! Morris Traversal은 O(1) 공간 복잡성에서 이 문제를 해결할 수 있습니다. 그러나 Morris Traversal은 읽기 까다롭고 어렵습니다. 단순화를 위해 여기서는 사용하지 않습니다.

리트코드 결과:

제출 링크 참조:

런타임: 56ms, Flatten Binary Tree to Linked List

에 대한 JavaScript 온라인 제출의 99.88%보다 빠름

메모리 사용량: 44.1MB, Flatten Binary Tree to Linked List에 대한 JavaScript 온라인 제출의 90.67% 미만

해결책

var flatten = function (root) {

    /* -------------------------------------------------------------------------- */
    /*                   114. Flatten Binary Tree to Linked List                  */
    /* -------------------------------------------------------------------------- */

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

    // So, we're not going to traverse the tree in pre-order traversal.
    // Instead, we're going to do the opposite of what we was just asked to do.
    // The reason for this is we're optimising for space complexity. If we did pre-order
    // traversal, we would have to store an entirely new tree in memory. While in this solution, we only store
    // the height of the tree in memory.

    // Do Post Order Traversal

    // Base case, empty node
    if (!root) {
        return null;
    }

    flatten(root.left);
    flatten(root.right);

    // Now, we're at the left most node,
    // We're going to ask if this current node
    // even has a left node?
    // If it does, move it's entire left sub tree
    // into the right tree but in-order. :D

    // Move the left tree to the right tree
    if (root.left) {
        // So, we're going to get the current left nodes
        // right most node. Because we're going to set this nodes
        // pointer to be the right node of the current node.
        let lefts_right_most_node = root.left;

        // Get me the left's right most node
        while (lefts_right_most_node.right) {
            lefts_right_most_node = lefts_right_most_node.right;
        }

        // Adjust the right most nodes pointer
        // to point to the current nodes right node
        lefts_right_most_node.right = root.right;

        // Add the left tree into the right tree.
        root.right = root.left;

        // Remove the left tree. We don't need it anymore.
        root.left = null;
    }

    return root;
};