平衡二叉树 - JZ39

题目描述

输入一棵二叉树，判断该二叉树是否是平衡二叉树。

平衡二叉树定义：

• 一个二叉树每个节点的左右两个子树的高度差的绝对值不超过1
• 左右子树都是平衡二叉树

示例：

输入: [3,9,20,null,null,15,7]
    3
   / \
  9  20
    /  \
   15   7
输出: true

输入: [1,2,2,3,3,null,null,4,4]
       1
      / \
     2   2
    / \
   3   3
  / \
 4   4
输出: false

解题思路

这道题有两种主要的解决方法：

方法一：自顶向下递归（暴力法）

1. 对于每个节点，计算左右子树的高度
2. 判断高度差是否不超过1
3. 递归检查左右子树是否平衡
4. 时间复杂度：O(n²)，空间复杂度：O(n)

方法二：自底向上递归（优化）

1. 后序遍历，先检查子树
2. 如果子树不平衡，直接返回-1
3. 如果子树平衡，返回高度并检查当前节点
4. 时间复杂度：O(n)，空间复杂度：O(n)

核心思想：

• 方法二避免了重复计算高度
• 一旦发现不平衡立即返回
• 利用返回值同时传递高度和平衡信息

项目结构

.
├── go.mod              # Go 模块定义
├── types.go            # 二叉树节点定义和工具函数
├── solution.go         # 算法实现（你需要完成这个文件）
├── answer.go           # 参考答案（练习后查看）
├── solution_test.go    # 单元测试
└── README.md          # 说明文档

使用方法

1. 实现算法

在 solution.go 文件中实现：

• isBalanced(root *TreeNode) bool - 主要实现
• isBalancedTopDown(root *TreeNode) bool - 自顶向下方法
• isBalancedBottomUp(root *TreeNode) bool - 自底向上方法

2. 运行测试

go test -v
go test -bench=.

时间和空间复杂度分析

方法	时间复杂度	空间复杂度	说明
自顶向下	O(n²)	O(n)	重复计算高度
自底向上	O(n)	O(n)	每个节点访问一次

知识点

• 二叉树遍历
• 递归思想
• 时间复杂度优化
• 平衡二叉树性质
• 后序遍历应用