솔루션 개발:

질문

이 기사에서는 Leetcode의 '563. Binary Tree Tilt' 질문을 다룰 것입니다.

의문:

Given the root of a binary tree, return the sum of every tree node's tilt.
The tilt of a tree node is the absolute difference between the sum of all left subtree node values and all right subtree node values. If a node does not have a left child, then
the sum of the left subtree node values is treated as 0. The rule is similar if the node does not have a right child.

예시:

Input: root = [1,2,3]
Output: 1
Explanation: 
Tilt of node 2 : |0-0| = 0 (no children)
Tilt of node 3 : |0-0| = 0 (no children)
Tilt of node 1 : |2-3| = 1 (left subtree is just left child, so sum is 2; right subtree is just right child, so sum is 3)
Sum of every tilt : 0 + 0 + 1 = 1

질문 설명

이 질문의 등급은 쉬움입니다. 나는 완전히 부정확하고 오해의 소지가 있다고 생각합니다.

이 질문은 중간 수준의 개념을 이해하는 경우에만 쉬운 것으로 간주될 수 있다고 생각합니다. 이진 트리를 합산하는 방법, 이진 트리를 순회하는 방법 및 재귀적으로 이진 트리를 순회하는 방법과 같습니다. Post Order Traversal은 무엇이며 트리 합계를 계산하는 데 어떻게 사용할 수 있습니까? 중간 수준의 개념을 이해하면 이 질문을 쉽게 이해할 수 있지만 질문 자체는 이러한 개념을 모르는 사람들을 위한 것이 아닙니다.

우리가 요구하는 것은 모든 노드의 왼쪽 및 오른쪽 하위 트리 합계 간의 차이를 계산하는 것입니다. 이는 다음과 같이 번역됩니다.
우리가 방문하는 모든 노드에서 왼쪽 트리와 오른쪽 트리의 합을 얻습니다. 둘 사이의 차이점을 파악하십시오. 그런 다음 그 차이를 총합에 더할 수 있습니다. 전체 트리의 모든 노드에 대해 이 프로세스를 반복합니다.

권장 지식

Binary Tree

Depth First Search

Post Order Traversal

Recursive Post Order Traversal

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

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

트리에서 각 노드의 기울기를 계산해야 합니다.

트리의 모든 노드를 방문해야 합니다.

Post Order Traversal을 사용하여 각 노드의 기울기를 계산해야 합니다.

어떻게 할 것인가:

Post Order Traversal을 사용하여 각 노드의 기울기를 계산할 것입니다. 왼쪽 및 오른쪽 하위 트리의 합을 계산하여 이를 수행합니다. 왼쪽 및 오른쪽 하위 트리의 합이 주어지면 현재 노드의 기울기를 계산할 수 있습니다.

기울기는 다음과 같이 계산됩니다.

tilt = abs(left_subtree_sum - right_subtree_sum)

트리에 있는 모든 노드의 전체 기울기를 저장하는 데 사용할 tilt_counter를 선언할 것입니다. 많은 ( += ) 작업.

우리는 Post Order Traversal

각 노드에서 현재 노드의 left_sum 및 right_sum를 얻습니다. 왼쪽 및 오른쪽 하위 트리의 합을 나타냅니다. (말이 안 되더라도 걱정하지 마세요. 곧 설명될 것입니다.)

그런 다음 현재 노드의 tilt를 계산합니다. left_sum 와 right_sum 사이의 절대 차이를 계산하여 이를 수행합니다. 그런 다음 이 값이 tilt_counter 에 추가됩니다.

그런 다음 현재 노드의 합계를 반환합니다. 현재 노드의 합은 (left_sum + right_sum + 현재 노드 합)으로 계산됩니다.

이를 계산한 후 해당 값을 반환합니다. Post Order Traversal 을 사용하고 있기 때문에 현재 노드의 합계를 트리 내의 부모 노드로 반환할 수 있습니다. 이것이 포인트 3에서 하위 트리 합계를 얻는 방법입니다.

빅오 표기법:

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

공간 복잡도: O(h) | 여기서 h는 이진 트리의 높이 | 내부 call stack 안에 트리의 높이를 저장할 것입니다.

리트코드 결과:

제출 링크 참조:

런타임: 79ms, Binary Tree Tilt에 대한 JavaScript 온라인 제출의 80.75%보다 빠름.

메모리 사용량: 47MB, Binary Tree Tilt에 대한 JavaScript 온라인 제출물의 85.45% 미만.

해결책

var findTilt = function (root) {

    /* -------------------------------------------------------------------------- */
    /*                            563. Binary Tree Tilt                           */
    /* -------------------------------------------------------------------------- */

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

    // Our tilt counter (Keeps track of the diff between the left and right subtrees)
    let tilt_counter = 0;

    // Recursive function to traverse the tree
    // In a post order fashion, get all the sums for all the subtrees
    // we then figure out the difference between the left and right subtrees
    // and add that to the tilt counter. 
    const post_order_traversal = (node) => {

        // If the node does not exist.
        // It has no value and therefore it's a 0.
        if (!node) {
            return 0;
        }

        // Post Order, get me their SUMS!!!
        let left_sum  = post_order_traversal(node.left);
        let right_sum = post_order_traversal(node.right);

        // Figure out the difference between the left and right subtrees
        // We use the absolute value of the difference to keep track of the tilt
        tilt_counter += Math.abs(left_sum - right_sum);

        // Return the value of the node and it's subtrees.
        return left_sum + right_sum + node.val;
    };

    post_order_traversal(root);
    return tilt_counter;
};