PHP怎么計算二叉樹坡度

本篇內(nèi)容介紹了“PHP怎么計算二叉樹坡度”的有關(guān)知識，在實際案例的操作過程中，不少人都會遇到這樣的困境，接下來就讓小編帶領(lǐng)大家學(xué)習(xí)一下如何處理這些情況吧！希望大家仔細(xì)閱讀，能夠?qū)W有所成！

一個樹某結(jié)點的坡度就是該結(jié)點左子樹的結(jié)點之和和右子樹結(jié)點之和的差的絕對值。今天我們就來聊聊計算二叉樹坡度的方法，有需要的可以參考參考。

給定一個二叉樹，計算整個樹的坡度。

一個樹的節(jié)點的坡度定義即為，該節(jié)點左子樹的結(jié)點之和和右子樹結(jié)點之和的差的絕對值?？战Y(jié)點的的坡度是0。

整個樹的坡度就是其所有節(jié)點的坡度之和。

示例：

輸入：
         1
       /   \
      2     3
輸出：1
解釋：
結(jié)點 2 的坡度: 0
結(jié)點 3 的坡度: 0
結(jié)點 1 的坡度: |2-3| = 1
樹的坡度 : 0 + 0 + 1 = 1

解題思路

遞歸遍歷二叉樹，累加 abs($left - $right) 的值，每次返回左右節(jié)點和當(dāng)前節(jié)點的和，用于下一次坡度計算。

php 代碼

/** 
* 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怎么計算二叉樹坡度”的內(nèi)容就介紹到這里了，感謝大家的閱讀。如果想了解更多行業(yè)相關(guān)的知識可以關(guān)注億速云網(wǎng)站，小編將為大家輸出更多高質(zhì)量的實用文章！