## 平衡二叉树 ### 定义 一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 ### 判断平衡二叉树 ~~~ /** * 平衡二叉树，以树形DP套路解决问题 * 一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。 * @Author: mango * @Date: 2022/4/11 9:33 下午 */ public class BalanceTree { public boolean isBalanced(TreeNode node){ return getInfo(node).isBalance; } // 递归手机信息 public Info getInfo(TreeNode node){ if(node == null){ return new Info(0,true); } // 搜集左树信息 Info leftInfo = getInfo(node.left); // 搜集右树信息 Info rightInfo = getInfo(node.right); // 高度等于左树和右树高的那个+1 int height = Math.max(leftInfo.height,rightInfo.height) + 1; // 是否平衡等于左右都平衡且高度相差小于2 boolean isBalance = leftInfo.isBalance && rightInfo.isBalance && Math.abs(leftInfo.height-rightInfo.height) < 2; return new Info(height,isBalance); } } // 信息体 class Info{ public int height; public boolean isBalance; public Info(int height,boolean isBalance){ this.height = height; this.isBalance = isBalance; } } ~~~