PHP怎么計算二叉樹坡度

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

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

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

一個樹的節點的坡度定義即為，該節點左子樹的結點之和和右子樹結點之和的差的絕對值。空結點的的坡度是0。

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

示例：

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

解題思路

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

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