## 平衡二叉樹 ### 定義 一個二叉樹每個節點 的左右兩個子樹的高度差的絕對值不超過 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; } } ~~~