## 满二叉树 ### 定义 每个节点都有左右孩子 ### 判断满二叉树 节点个数 = 2 ^ 数最大高度 - 1 ~~~ /** * 判断满二叉树：节点个数 = 2^最大深度 - 1 * @Author: mango * @Date: 2022/4/14 10:00 下午 */ public class FullTree { public boolean isFullTree(TreeNode root) { FullInfo info = process(root); return info.nodeCount == Math.pow(2,info.height) - 1; } public FullInfo process(TreeNode node){ if(node == null){ return new FullInfo(0,0); } FullInfo left = process(node.left); FullInfo right = process(node.right); // 高度 = 左树或者右树较高的高度 + 当前节点高度1 int height = Math.max(left.height,right.height) + 1; // 节点数 = 左树节点数 + 右树节点数 + 当前节点1 int nodeCount = left.nodeCount + right.nodeCount + 1; return new FullInfo(height,nodeCount); } } class FullInfo{ public int height; public int nodeCount; public FullInfo(int height, int nodeCount) { this.height = height; this.nodeCount = nodeCount; } } ~~~