110. 平衡二叉树

110. 平衡二叉树

给定一个二叉树,判断它是否是高度平衡的二叉树。

本题中,一棵高度平衡二叉树定义为:

一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1。

示例 1:

给定二叉树 [3,9,20,null,null,15,7]

    3
   / \
  9  20
    /  \
   15   7

返回 true 。 示例 2:

给定二叉树 [1,2,2,3,3,null,null,4,4]

       1
      / \
     2   2
    / \
   3   3
  / \
 4   4

返回 false

题目难度: 简单

第一版本:

根据定义

1 遍历 treeo o(n)

2 然后计算每个节点的深度 o(n)

3 如果当前节点为不满足定义 false 整个tree就是不平衡的二叉树

time:o(n*2)

正如西部世界 故事线有2个故事性

世界分为三条线,两实一虚: 1. 当前时间线: 黑帽威廉时间线,凡是有黑帽威廉的都在当前时间 2. 历史时间线:白帽威廉时间线 (35年前),凡是有白帽威廉的都在历史时间,属于回忆 3. 虚拟时间线: 女主脑海中的闪回,脑补画面,与时间没直接关系,可在多个时间线跳跃,也可以是完全脑补的画面。 当女主是穿蓝色的连衣裙、自言自语时属于这条虚拟时间线。

求平衡二叉树2个故事

  • 一个是遍历tree判断是否平衡的二叉树
  • 一个是遍历tree求深度

第二版本:

golang 通过函数多个参数的返回值 返回从下到上传递的数据

测试异常

 /递归判断是否平衡二叉树 root left right 节点都平衡
 bRoot := math.Abs(float64(dLeft)-float64(dRight)) >1   
应该是求判断是否符合条件

c++ 通过引用传递 返回从下到上传递的数据

总结:

体会到了 c++ 引用传参 和golang 返回多个参数各种优点


原文发布于微信公众号 - 架构说(JiaGouS)

原文发表时间:2018-05-09

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏HansBug's Lab

3361: [Usaco2004 Jan]培根距离

3361: [Usaco2004 Jan]培根距离 Time Limit: 10 Sec  Memory Limit: 128 MB Submit: 16  S...

36150
来自专栏追不上乌龟的兔子

[奇怪但有用的数据结构]并查集Union Find

严格来讲并查集并不是一个数据结构,而是一个算法,毕竟其英文名直译是联合查找,但作为一个系列,还是当做数据结构讲了。

99870
来自专栏行者悟空

利用Hadoop Mapreduce实现pv统计分析

37030
来自专栏数据结构与算法

BZOJ2152: 聪聪可可(点分治)

聪聪和可可是兄弟俩,他们俩经常为了一些琐事打起来,例如家中只剩下最后一根冰棍而两人都想吃、两个人都想玩儿电脑(可是他们家只有一台电脑)……遇到这种问题,一般情况...

11830
来自专栏aCloudDeveloper

string 之 strlen函数

Author: bakari  Date: 2012/8/9 近两年好多的IT公司喜欢拿一些库函数来考,string函数库当然是首选,除此之外,像qsort,S...

22070
来自专栏章鱼的慢慢技术路

牛客网2018年全国多校算法寒假训练营练习比赛(第二场)

38840
来自专栏C语言及其他语言

OJ系统(ACM/NOI)的基本输入输出教程

在介绍OJ系统之前,首先为大家介绍一下ACM: ACM原代表美国计算机协会,因其举办的ICPC即国际大学生程序设计竞赛而闻名全世界,此项赛事要求学生的在五小时内...

699120
来自专栏HTML5学堂

揭开身份证验证的神秘面纱

正则验证身份证号码 HTML5学堂:曾经一直觉得用正则验证身份证号码是很简单的~但是,当真正挖掘身份证号码的规则之后,才发现,想要写好一个正则验证也没有那么容易...

50150
来自专栏lonelydawn的前端猿区

Node.js力破江苏网警刑侦科推理试题

月前,江苏网警 在微博发布了一套《2018年刑侦科目推理试题》,可谓难倒了诸多英雄好汉,评论区内更是一片皮皮之音。 @二向箔icon: 高考前班主任教过我们,...

35470
来自专栏数据结构与算法

Day3上午解题报告

预计分数:100+40+50=190 实际分数:100+40+50=190 T1 https://www.luogu.org/problem/show?pid=...

30550

扫码关注云+社区

领取腾讯云代金券