算法题(二叉树):平衡二叉树
题目描述
输入一棵二叉树，判断该二叉树是否是平衡二叉树。
在这里，我们只需要考虑其平衡性，不需要考虑其是不是排序二叉树
解答
平衡二叉树定义(AVL)：它或者是一颗空树，或者具有以下性质的二叉排序树：它的左子树和右子树的深度之差(平衡因子)的绝对值不超过1，且它的左子树和右子树都是一颗平衡二叉树。
图一中左边二叉树的节点45的左孩子46比45大，不满足二叉搜索树的条件，因此它也不是一棵平衡二叉树。
右边二叉树满足二叉搜索树的条件，同时它满足条件二，因此它是一棵平衡二叉树。
左边二叉树的节点45左子树高度2，右子树高度0，左右子树高度差为2-0=2，不满足条件二；
右边二叉树的节点均满足左右子树高度差至多为1，同时它满足二叉搜索树的要求，因此它是一棵平衡二叉树。
我们可以计算出树的高度int hightdepth(TreeNode root) {if (root == null) {return 0;}int ldep = depth(root.left);int rdep = depth(root.right);return 1 + (ldep > rdep ? ldep : rdep);}然后对上述代码加以改造，如果不满足平衡二叉树的定义，则返回-1，并且如果左子树不满足条件了，直接返回-1，右子树也是如此，相当于剪枝，加速结束递归。/*** 时间复杂度：O(N)* 空间复杂度：O(N)** @param root* @return*/public int depth(TreeNode root) {if (root == null) {return 0;}int left = depth(root.left);if (left == -1) {return -1;//如果发现子树不平衡之后就没有必要进行下面的高度的求解了}int right = depth(root.right);if (right == -1) {return -1;//如果发现子树不平衡之后就没有必要进行下面的高度的求解了}if (left - right < -1 || left - right > 2) {return -1;} else {return 1 + (left > right ? left : right);}}public boolean IsBalance_Solution(TreeNode treeNode) {return depth(treeNode) != -1;}
ps: 想要查看之前的文章都已经保存
- THE END -
作者简介
Mr.W
白天搬砖，晚上砌梦想。
相信每个人有故事，程序员更是有许多事故，书写最接地气的程序员故事,为大家找出更好的资料。