剑指offer54_平衡二叉树
平衡二叉树
输入一棵二叉树的根结点，判断该树是不是平衡二叉树。
如果某二叉树中任意结点的左右子树的深度相差不超过 1，那么它就是一棵平衡二叉树。
注意：
- 规定空树也是一棵平衡二叉树。
数据范围
树中节点数量 [0,500][0,500][0,500]。
样例
输入：二叉树[5,7,11,null,null,12,9,null,null,null,null]如下所示，5/ \7 11/ \12 9输出：true
算法思路
该算法用于判断给定的二叉树是否是平衡的。平衡二叉树的定义是：对于树中的任意节点，其左子树和右子树的高度差不超过1。
- 深度优先搜索（DFS）：算法采用后序遍历的方式递归地计算每个节点的左右子树高度。
- 高度差检查：在递归过程中，比较当前节点的左右子树高度差，如果超过1，则将全局变量
ans设为false。 - 返回高度：每个递归调用返回当前节点的高度（左右子树高度的最大值加1），供父节点使用。
时间复杂度
- O(n)：其中n是二叉树的节点数。每个节点仅被访问一次，因此时间复杂度是线性的。
空间复杂度
- O(h)：其中h是二叉树的高度。空间复杂度主要由递归调用栈的深度决定，最坏情况下（树完全不平衡）为O(n)，最好情况下（树完全平衡）为O(log n)。
/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode(int x) : val(x), left(NULL), right(NULL) {}* };*/
class Solution {
public:bool ans = true; // 全局变量，用于记录树是否平衡bool isBalanced(TreeNode* root) {dfs(root); // 从根节点开始深度优先搜索return ans; // 返回结果}// 辅助函数：计算节点高度并检查平衡性int dfs(TreeNode* root) {if (!root) return 0; // 空节点高度为0int l = dfs(root->left); // 递归计算左子树高度int r = dfs(root->right); // 递归计算右子树高度if (abs(l - r) > 1) ans = false; // 如果高度差超过1，树不平衡return max(l, r) + 1; // 返回当前节点的高度}
};
关键点
- 后序遍历：先处理左右子树，再处理当前节点，确保高度计算正确。
- 全局变量
ans：用于在递归过程中记录是否发现不平衡的节点。 - 高度差检查：在每次递归返回高度前，检查左右子树高度差。