一 、 递归套路解决判断完全二叉树

1.1 描述

1.2 分析

1.3 代码

public static boolean isCBT2(Node head) {return process(head).isCBT;}public static class Info {public boolean isFull;public boolean isCBT;public int height;public Info(boolean full, boolean cbt, int h) {isFull = full;isCBT = cbt;height = h;}}public static Info process(Node x) {if (x == null) {return new Info(true, true, 0);}Info leftInfo = process(x.left);Info rightInfo = process(x.right);int height = Math.max(leftInfo.height, rightInfo.height) + 1;boolean isFull = leftInfo.isFull && rightInfo.isFull && leftInfo.height == rightInfo.height;boolean isCBT = false;if (leftInfo.isFull && rightInfo.isFull && leftInfo.height == rightInfo.height) {isCBT = true;} else if (leftInfo.isCBT && rightInfo.isFull && leftInfo.height == rightInfo.height + 1) {isCBT = true;} else if (leftInfo.isFull && rightInfo.isFull && leftInfo.height == rightInfo.height + 1) {isCBT = true;} else if (leftInfo.isFull && rightInfo.isCBT && leftInfo.height == rightInfo.height) {isCBT = true;}return new Info(isFull, isCBT, height);}