• 技术文章 >后端开发 >PHP问题

    PHP如何计算二叉树坡度

    醉折花枝作酒筹醉折花枝作酒筹2021-07-09 15:21:52转载107
    一个树某结点的坡度就是该结点左子树的结点之和和右子树结点之和的差的绝对值。今天我们就来聊聊计算二叉树坡度的方法,有需要的可以参考参考。

    给定一个二叉树,计算整个树的坡度。

    一个树的节点的坡度定义即为,该节点左子树的结点之和和右子树结点之和的差的绝对值。空结点的的坡度是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视频教程

    以上就是PHP如何计算二叉树坡度的详细内容,更多请关注php中文网其它相关文章!

    声明:本文转载于:何晓东的博客,如有侵犯,请联系admin@php.cn删除
    专题推荐:PHP
    上一篇:PHP不使用加减乘除运算符号如何实现加法 下一篇:PHP如何判断是否为平衡二叉树
    VIP会员

    相关文章推荐

    • php rewrite是什么意思• linux环境下php7.0怎么安装• php unserialize 失败怎么办• PHP中Direct IO扩展的安装使用• PHP不使用加减乘除运算符号如何实现加法

    全部评论我要评论

  • 取消发布评论发送
  • 1/1

    PHP中文网