平衡二叉树及其判断

平衡二叉树

出现：对于一颗二叉树的搜索，期望时间复杂度为O(lng2（n）)。但是对于某些极端的树结构，如存储结构直接是一条链，这时它的时间复杂度就会退为O(n)。会大幅度的降低操作时的效率。因此，便引入了平衡二叉树。
Balanced Binary Tree：是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。

平衡二叉树的判断

严格按照其定义进行判断：
①空树为平衡二叉树；
②左右子树高度差不超过1；
③左右子树皆为平衡二叉树。

所以，需先建立一个函数用以统计当前结点的高度。
计算当前结点高度
使用递归来完成统计，递归出口：结点为空，高度为0

/*** 获取当前结点的高度* @param rootNode* @return*/public static int depth(TreeNode rootNode) {//递归出口if(rootNode == null) {return 0;}//左右子树高度int lDepth = depth(rootNode.getLeChild());int rDepth = depth(rootNode.getRiChild());//返回较大值加一return (lDepth > rDepth? lDepth : rDepth)+1;}

判断当前结点是否平衡
当满足①或②③时平衡，所以在判断②时只判断不符合就返回，是否平衡还需判断③

/*** 判断以该结点为根的树是否为平衡二叉树* @param rootNode  判断结点* @return   是否平衡*/public static boolean isBalance(TreeNode rootNode) {//深度为0的树也是平衡二叉树if(rootNode == null) {return true;}//判断左右子树深度 int lDepth = depth(rootNode.getLeChild());int rDepth = depth(rootNode.getRiChild());int diValue = lDepth - rDepth;if(diValue > 1 || diValue < -1) {return false;}//判断左右子树是否为平衡二叉树return isBalance(rootNode.getLeChild())&&isBalance(rootNode.getRiChild());  }

有关判断算法的更优解

不难发现之前的判断算法
先判断根左右子树深度，这时会调用depth进行递归判断，
再递归判断左右子树，在其内部也会调用depth进行递归判断
这会导致对深部结点进行重复运算，使得算法效率降低

因此，可以先判断左右子树是否平衡
如果左右子树有一个不是平衡子树，则对于根结点的左右深度对比也是没有必要

平衡二叉树口诀，同时，由于判断子树平衡时，使用递归，是自下向上进行判断的。使用动态规划，定义一个引用，在判断子树是否平衡的同时，记录子树的深度，使得不再花费时间再次访问子树

/*** 使用一个参数对其深度进行记录，先判断左右子树，再使用参数判断根* 即后序遍历进行判断* 此处由于java 中普通类型无法使用引用直接对内存进行访问，* 因此使用数组，定义长度为一，即可传入数组的引用* @param rootNode  判断结点* @return  是否平衡*/public static boolean optiBalance(TreeNode rootNode,int[] depth) {if(rootNode == null) {//深度为0，深度归0depth[0] = 0;return true;}int[] lDepth = new int[1];int[] rDepth = new int[1];lDepth[0] = rDepth[0] = depth[0];  //赋初值 if(optiBalance(rootNode.getLeChild(), lDepth) && optiBalance(rootNode.getRiChild(), rDepth)){int diValue = lDepth[0] - rDepth[0];if(diValue <= 1 && diValue >= -1) {depth[0] = (lDepth[0] > rDepth[0]? lDepth[0] : rDepth[0])+1;return true;}}return false;}