day144—递归—平衡二叉树（LeetCode-110）

题目描述

给定一个二叉树，判断它是否是 平衡二叉树

示例 1：

输入：root = [3,9,20,null,null,15,7]输出：true

示例 2：

输入：root = [1,2,2,3,3,null,null,4,4]输出：false

示例 3：

输入：root = []输出：true

提示：

• 树中的节点数在范围[0, 5000]内
• -104 <= Node.val <= 104

解决方案：

这段代码的核心功能是判断一棵二叉树是否为平衡二叉树（即每个节点的左右子树高度差的绝对值不超过 1），采用「后序遍历 + 递归剪枝」的思路实现，在计算子树高度的同时校验平衡条件，时间复杂度O(n)（n为节点数），空间复杂度O(h)（h为树的高度），是该问题的最优解法。

核心逻辑

代码将 “计算子树高度” 和 “校验平衡条件” 融合在同一个递归函数中，通过返回特殊值-1实现剪枝，避免重复遍历：

1. 递归辅助函数node_height：既计算节点的高度，又实时校验平衡条件：
   • 边界条件：空节点高度为0；
   • 递归计算左子树高度left_h，若左子树已不平衡（left_h=-1），直接返回-1（剪枝，无需计算右子树）；
   • 同理递归计算右子树高度right_h，若右子树不平衡，直接返回-1；
   • 校验当前节点平衡条件：若左右子树高度差的绝对值 > 1，返回-1（标记当前子树不平衡）；
   • 若平衡，返回当前节点的高度（max(left_h, right_h)+1）；
2. 主函数isBalanced：
   • 空树直接返回true（空树是平衡的）；
   • 调用node_height(root)，若返回值不为-1，说明整棵树平衡，返回true，否则返回false。

总结

1. 核心思路：后序遍历（先算左右子树高度，再判断当前节点），在计算高度的同时校验平衡，用-1剪枝避免无效递归；
2. 关键优化：相比 “先算所有节点高度，再逐个校验” 的暴力解法，该思路只需一次遍历，时间效率更高；
3. 效率特点：每个节点仅被访问一次，时间O(n)；递归栈空间取决于树的高度，平衡树为O(log n)，退化为链表时为O(n)。

函数源码：

/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: int node_height(TreeNode* node){ if(!node) return 0; int left_h=node_height(node->left); if(left_h==-1){ return -1; } int right_h=node_height(node->right); if(right_h==-1){ return -1; } if(abs(right_h-left_h)>1){ return -1; } return max(left_h,right_h)+1; } bool isBalanced(TreeNode* root) { if(!root) return true; return node_height(root)!=-1; } };