判断一个二叉树是不是满二叉树
代码实现
/** * 满二叉树 * 判断方法:先得到数的最大深度l,在得到数的所有节点数N * 如果满足N = 2^l - 1,则是满二叉树 * @author zyt * */ public class FullBinaryTree { //手动定义二叉树的节点类型 public static class Node{ public int value; public Node left; public Node right; public Node(int data){ this.value = data; } } //用二叉树的套路方法去求解 public static boolean isF(Node head){ //如果是空的,则是满二叉树 if(head == null){ return true; } //获取整棵树的深度和节点个数 Info data = f(head); return data.nodes == (1 << data.height - 1); //N = 2^l - 1 } //定义一个返回类型 public static class Info{ public int height;//二叉树的深度 public int nodes;//二叉树的节点个数 public Info(int h, int n){ height = h; nodes = n; } } public static Info f(Node x){ if(x == null){ return new Info(0, 0); } //从左子树获取信息 Info leftData = f(x.left); //从右子树获取信息 Info rightData = f(x.right); //收集以当前节点为头节点的二叉树的信息 int height = Math.max(leftData.height, rightData.height) + 1; int nodes = leftData.nodes + rightData.nodes + 1; return new Info(height, nodes); } }
下一篇:
华为机试练习(五)喊7的次数重排