日本語
日本語
バイナリツリーは、ノードで構成される一般的なデータ構造であり、各ノードには最大2つの子ノードがあります。通常、左の子ノードの値は、右の子ノードの値よりも小さくなります。バイナリツリーは、バイナリツリーの検索、バランスの取れたバイナリツリー、ヒープなど、コンピューターサイエンスで広く使用されています。この記事では、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;
}
// バイナリツリースロープを計算する深度first検索
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を介してバイナリツリーの勾配を計算する方法について説明します。深さ-first検索アルゴリズムを使用して、各ノードを再帰的に通過し、ノード勾配を計算して蓄積し、最後にツリー全体の勾配を取得します。アルゴリズムにはO（n）の時間複雑さがあります。これは、バイナリツリースロープの問題に対処するための効率的な方法です。
