솔루션 개발:

질문

이 기사에서는 Leetcode의 '814. Binary Tree Pruning' 질문에 대해 다룰 것입니다. 이 질문은 보통 질문으로 평가됩니다.

의문:

Given the root of a binary tree, return the same tree where every subtree (of the given tree) not containing a 1 has been removed.

A subtree of a node is a node plus every node that is a descendant of node.

예시:

Input: root = [1,null,0,0,1]
Output: [1,null,0,null,1]
Explanation: 
Only the red nodes satisfy the property "every subtree not containing a 1".
The diagram on the right represents the answer.

질문 설명

이 질문의 등급은 보통입니다. 질문이 잘못 표현되었지만 이진 트리가 주어졌고 1을 포함하지 않는 모든 하위 트리를 제거해야 한다는 것은 분명합니다.

기본적으로 우리가 묻는 것은 '이 하위 트리에 1이 포함되어 있습니까?'입니다. 그렇다면 보관하십시오. 그렇지 않은 경우 제거하십시오.

이 질문의 까다로운 부분은 이것을 달성하기 위해 어떤 종류의 순회가 필요한지 알아내는 것입니다. 그러나 전체 하위 트리에 1이 포함되어 있는지 알아야 하므로 Post Order Traversal을 사용하여 이를 달성할 수 있습니다. 모든 하위 트리의 맨 아래에서 시작하여 위로 올라가면 하위 트리에 1이 포함되어 있는지 알 수 있습니다.

권장 지식

Binary Tree

Depth First Search

Post Order Traversal

Recursion

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

이진 트리가 있습니다.

이 이진 트리에는 1 또는 0만 포함되어 있습니다.

모든 하위 트리에 1 또는 0이 포함되어 있는지 확인해야 합니다. 이는 무차별 대입 솔루션을 방지하기 위해 트리 맨 아래에서 시작하여 위로 작업해야 함을 의미합니다.

어떻게 할 것인가:

Post Order Traversal을 사용하여 맨 아래에서 시작하여 트리를 탐색할 것입니다. 부모 노드를 확인하기 전에 각 하위 트리를 확인하기를 원하기 때문에 이렇게 합니다. 즉, 부모 노드를 확인할 때 자식 노드에 1가 포함되어 있는지 이미 알고 있습니다.

Post Order Traversal 및 트리 맨 아래에서 시작

현재 노드가 빈 노드인지 묻습니다. 그렇다면 어린이용으로 1을 가질 수 없습니다. 따라서 가지치기가 필요한 것으로 이 하위 트리를 보고합니다.

그런 다음 왼쪽 트리 또는 오른쪽 트리에 1s가 포함되어 있는지 묻습니다. 그렇지 않은 경우 무효화하여 이 트리를 가지치기합니다

.

그런 다음 1이 포함된 하위 항목이 있는지 묻습니다. 하위 트리 어딘가에 하나가 존재하는 상위 노드까지 결과를 버블링할 수 있도록 이렇게 합니다. 전체 하위 트리의 가지치기를 방지하기 위해 이렇게 합니다.

모든 노드가 확인될 때까지 이 프로세스를 반복합니다.

새로 가지치기한 나무를 반환합니다.

빅오 표기법:

시간 복잡도: O(n) | 여기서 n은 이진 트리의 노드 수 | 트리가 모두 '1'인 최악의 시나리오에서 트리 내의 모든 노드를 순회할 것이기 때문입니다.

공간 복잡도: O(h) | 여기서 h는 이진 트리의 높이 | Call Stack로 인해 post order traversal 내에 트리의 높이를 저장할 것이기 때문입니다.

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

리트코드 결과:

제출 링크 참조:

런타임: 90ms, 이진 트리 가지치기

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

메모리 사용량: 42.1MB, 이진 트리 가지치기에 대한 JavaScript 온라인 제출물의 92.19% 미만

해결책

 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 * this.val   = (val===undefined ? 0 : val)
 * this.left  = (left===undefined ? null : left)
 * this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {TreeNode}
 */
var pruneTree = function (root) {

    /* -------------------------------------------------------------------------- */
    /*                          814. Binary Tree Pruning                          */
    /* -------------------------------------------------------------------------- */

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

    // So how are we going to do it?
    // > We're going to perform post-order traversal
    // > where we ask every node:
    // > - Does your left tree have a 1 anywhere?
    // > - Does your right tree have a 1 anywhere?
    // > - If it has no 1, we prune it.
    // > - If any of them have a one, we let the parent node know

    const post_order_prune = (node) => {

        // End of tree. So of course, this tree has no 1s
        if (!node) {
            return false;
        }

        // Do either the right or left nodes have 1s?
        let left_contains_a_one  = post_order_prune(node.left);
        let right_contains_a_one = post_order_prune(node.right);

        // Left tree hasn't got a 1
        if (!left_contains_a_one) {
            // Prune it
            node.left = null;
        }

        // Right tree does not have a 1
        if (!right_contains_a_one) {
            // Prune it
            node.right = null;
        }

        // So did any of our trees contain a 1?
        // Let the parent know about this.
        // We do this because, you could have a 1 all the way the bottom of the tree.
        // Which we need to bubble all the way back up to the parent.
        if (left_contains_a_one || right_contains_a_one) {
            return true;
        }

        // After pruning
        // Return this nodes value (Truthy or falsely)
        return node.val;
    };

    // Start the prune of children
    post_order_prune(root);

    // So we have pruned the children, does the root node
    // need to be removed?
    if (!root.right && !root.left && root.val === 0) {
        root = null;
    }

    // Return the root
    return root;
};