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 返回多个参数各种优点