【LeetCode经典题解】平衡二叉树高效判断：从O(n²)到O(n)优化
🎁个人主页：User_芊芊君子
🎉欢迎大家点赞👍评论📝收藏⭐文章
🔍系列专栏：Java.数据结构
【前言】
在数据结构的知识体系里，平衡二叉树是确保二叉树各类操作高效执行的关键存在。力扣平台上“判断二叉树是否为平衡二叉树”这一经典问题，看似解法直观，实则能通过不同的解题思路，清晰展现出算法效率的天差地别，从最开始直观却低效的递归方式，到经过巧妙优化后的高效递归策略，背后蕴含着对平衡二叉树本质的深度剖析与精准把握。
这里写目录标题
一、平衡二叉树
平衡二叉树又称AVL树：当一棵空树或者它的左右两棵字数的高度差的绝对值不超过一，并且两棵子树都是平衡二叉树
【注意】
任意节点的左右子树高度差不超过一；所以子树都满足平衡条件；
二、思路分析
方法一：时间复杂度为O(n^2)
首先判断根节点是否为空，跟节点为空的话，是平衡二叉树；然后就是用getHigh()方法获取左右子树的高度；判断他们的高度差的绝对值小于等于1的话，还要递归左右子树，左右子树平衡就是平衡二叉树，；时间复杂度为O(n^2)，因为计算高度时会重复遍历子树，每个节点都要求一次高度
方法二：时间复杂度为O(n)
先判断根节点是否为空，为空就是平衡二叉树；不为空调用getHigh()方法，通过判断getHigh()的返回值是否大于等于0来判断是否平衡；getHigh()方法计算二叉树高度的同时，判断树是否平衡，平衡返回树的高度，不平衡返回-1时间复杂度为O(n)，n是二叉树节点，==每个节点只被访问一次，计算高度和判断平衡的操作都是O(1)；三、代码展示
publicbooleanisBalanced(TreeNode root){if(root ==null){returntrue;}int leftH =getHigh(root.left);int rightH =getHigh(root.right);returnMath.abs(leftH - rightH)<=1&&isBalanced(root.left)&&isBalanced(root.right);}publicintgetHigh(TreeNode root){if(root ==null){return0;}int leftH =getHigh(root.left);int rightH =getHigh(root.right);return leftH > rightH ? leftH+1: rightH+1;}publicbooleanisBalanced(TreeNode root){if(root ==null){returntrue;}returngetHigh(root)>=0;}publicintgetHigh(TreeNode root){if(root ==null){return0;}int leftH =getHigh(root.left);if(leftH <0){return-1;}int rightH =getHigh(root.right);if(leftH >=0&& rightH >=0&&Math.abs(leftH - rightH)<=1){return leftH > rightH ? leftH+1: rightH+1;}else{return-1;}}四、总结
“自顶向下”的递归方法虽然思路直观易懂，但由于在计算过程中会重复去计算子树的高度，导致时间复杂度达到了O(n^2)，在处理大规模数据时显得力不从心；而“自底向上”的递归方法，借助后序遍历的顺序，在计算子树高度的同时就完成了平衡与否的判断，还利用提前终止递归的技巧避免了重复计算，成功将时间复杂度优化到O(n)，这一过程很好地体现了在算法设计中，通过调整执行逻辑、复用中间计算结果，能够显著提升算法效率的核心思想。
