PHP에서 이진 트리의 기울기를 계산하는 방법

트리 노드의 기울기는 왼쪽 하위 트리 노드의 합과 오른쪽 하위 트리 노드의 합 간의 차이의 절대값입니다. 오늘은 이진트리의 기울기를 계산하는 방법에 대해 이야기해보겠습니다. 필요하시면 참고하시면 됩니다.

이진 트리가 주어지면 전체 트리의 기울기를 계산하세요.

트리 노드의 기울기는 왼쪽 하위 트리 노드의 합과 해당 노드의 오른쪽 하위 트리 노드의 합 간의 차이의 절대값으로 정의됩니다. 빈 노드의 기울기는 0입니다.

전체 트리의 기울기는 모든 노드의 기울기의 합입니다.

예:

输入：
         1
       /   \
      2     3
输出：1
解释：
结点 2 的坡度: 0
结点 3 的坡度: 0
结点 1 的坡度: |2-3| = 1
树的坡度 : 0 + 0 + 1 = 1

문제 해결 아이디어

이진 트리를 재귀적으로 탐색하고, abs($left - $right) 값을 누적하고, 매번 왼쪽 및 오른쪽 노드와 현재 노드의 합을 반환합니다. 다음 경사 계산을 위해

php code

/** 
* Definition for a binary tree node. 
* class TreeNode { 
* public $val = null; 
* public $left = null; 
* public $right = null; 
* function __construct($value) { 
    $this->val = $value; 
    } 
 * } 
 */
class Solution {

    /** * @param TreeNode $root * @return Integer */
    private $total = 0;
    function findTilt($root) {
        $this->traverse($root);

        return $this->total;
    }

    function  traverse($root) {
        if($root == null) {
            return 0;
        }
    
        $left = $this->traverse($root->left);
        $right = $this->traverse($root->right);
        $this->total += abs($left - $right);

        return $left + $right + $root->val;
    }
}

추천 학습: php 비디오 튜토리얼

위 내용은 PHP에서 이진 트리의 기울기를 계산하는 방법의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!