How to calculate the slope of a binary tree in PHP

The slope of a node of a tree is the absolute value of the difference between the sum of the nodes of the left subtree of the node and the sum of the nodes of the right subtree. Today we will talk about the method of calculating the slope of a binary tree. You can refer to it if you need it.

Given a binary tree, calculate the slope of the entire tree.

The slope of a tree node is defined as the absolute value of the difference between the sum of the nodes of the left subtree of the node and the sum of the nodes of the right subtree. The slope of an empty node is 0.

The slope of the entire tree is the sum of the slopes of all its nodes.

Example:

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

Problem-solving ideas

Recursively traverse the binary tree, accumulate the values ​​​​of abs($left - $right), and return left and right each time The sum of the node and the current node is used for the next slope calculation.

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;
    }
}

Recommended learning: php video tutorial

The above is the detailed content of How to calculate the slope of a binary tree in PHP. For more information, please follow other related articles on the PHP Chinese website!