Skip to content

14311: 【原4311】二叉树的倾斜度

题目

题目描述

author: liquor233 原OJ链接:https://acm.sjtu.edu.cn/OnlineJudge-old/problem/4311

Description

二叉树的倾斜度定义如下:

  1. 当前结点的倾斜度为左子树所有结点值的和与右子树所有结点值的和的差值的绝对值,如左子树的结点有1、3、5,右子树的结点有2、10,则该父结点的倾斜度为3。叶结点的倾斜度为0,如果一个结点仅有左子树/右子树,则该结点的倾斜度为其左子树/右子树结点值的和。

  2. 树的倾斜度为所有结点倾斜度的和。

根据此定义,给定一棵二叉树,求出该树的倾斜度。

Input Format

输入的数据形式为二叉树层次遍历的结果,输出到最后一个叶结点结束,在此叶结点之前的空结点,使用-1表示。如一棵树,根节点为1,其右子结点为2,2的左子结点为3,则输入数据为1 -1 2 -1 -1 3

输入数据为两行,第一行是层次遍历序列的个数n,第二行是层次遍历的序列,以空格分隔开

数据具有以下特点

  1. 长度不超过5000

  2. 结点值为正整数,结点值不超过5000

  3. 每个结点的值都不相同

  4. 树不一定是满二叉树

Output Format

求出的倾斜度,以整数表示

Sample Input

15

1 2 3 -1 -1 4 5 -1 -1 -1 -1 6 -1 -1 7

Sample Output

28

Oops! 本题目还没有解答!

助教老师们编题的速度,已经超过了解题的速度!

OJ翻了一新,但本解答集还大多用的是2017-2019级,甚至更早的同学们贡献的答案。

如果你已经AC了,可以的话,请您参考添加页面,与大家一起分享你的题解!