이진 트리의 기울기 계산 방법 -PHP 구현 분석

이진 트리 개요

이진 트리는 노드로 구성된 공통 데이터 구조이며 각 노드에는 최대 두 개의 자식 노드가 있습니다. 일반적으로 왼쪽 하위 노드의 값은 오른쪽 하위 노드의 값보다 작습니다. 이진 나무는 이진 나무, 균형 이진 나무 및 더미 검색과 같은 컴퓨터 과학에서 널리 사용됩니다. 이 기사는 PHP를 통해 이진 트리의 기울기를 계산하는 방법을 설명합니다.

이진 트리 경사는 무엇입니까?

이진 트리 슬로프는 왼쪽 하위 트리의 노드 값의 합계와 각 노드의 오른쪽 하위 트리 사이의 차이의 절대 값을 나타냅니다. 이진 트리의 기울기는 모든 노드의 경사의 합입니다.

PHP 코드 구현

 
/**
 * 이진 트리 노드 정의
 * class TreeNode {
 *     public $val = null;
 *     public $left = null;
 *     public $right = null;
 *     function __construct($value) { $this->val = $value; }
 * }
 */
class Solution {
    public $res = 0;

    function findTilt($root) {
        $this->dfs($root);
        return $this->res;
    }

    // 이진 트리 슬로프를 계산하기위한 깊이 우선 검색
    function dfs($root) {
        if ($root == null) return 0;
        $left = $this->dfs($root->left);
        $right = $this->dfs($root->right);
        $this->res += abs($left - $right);
        return $left + $right + $root->val;
    }
}

위의 PHP 코드는 바이너리 트리 클래스를 구현하고 DFS 깊이 우선 검색을 통해 노드를 가로 질러 각 노드의 기울기를 계산합니다. 기능 FindTilt는 전체 바이너리 트리의 슬로프 합을 반환하는 데 사용됩니다. DFS 함수는 각 노드를 재귀 적으로 가로 지르고 왼쪽 하위 트리의 합계와 현재 노드의 오른쪽 하위 트리를 반환합니다.

알고리즘 분석

이진 트리 슬로프를 계산하는 프로세스는 모든 노드를 가로 지르고 각 노드의 왼쪽과 오른쪽 하위 트리의 차이의 절대 값을 계산해야합니다. 트래버스 프로세스 동안, 각 노드의 기울기 값이 축적되고 전체 이진 트리의 경사가 마침내 얻어집니다.

이 계산을 달성하기 위해 재귀 방법을 사용하여 이진 트리를 바닥에서 횡단합니다. 각 노드에 대해 왼쪽 및 오른쪽 서브 트리의 경사가 먼저 계산 된 다음 차이의 절대 값이 총 기울기에 추가됩니다.

시간 복잡성은 O (n)이며, 여기서 n은 이진 트리의 노드 수입니다.

요약

이 기사에서는 PHP를 통해 이진 트리의 기울기를 계산하는 방법에 대해 설명합니다. 깊이 우선 검색 알고리즘을 사용하여 각 노드를 재귀 적으로 통과하고 노드 경사를 계산하고 축적 한 다음 마지막으로 전체 트리의 경사를 얻습니다. 알고리즘은 O (n)의 시간 복잡성을 가지고 있으며, 이는 이진 트리 슬로프 문제를 처리하는 효율적인 방법입니다.