首页 >> 网页技术 > 编程技术 >> 详细内容
网页技术
 
编程技术 >> 正文
Java 实现平衡二叉树
日期：2018/5/9 

输入一棵二叉树，判断该二叉树是否是平衡二叉树。

平衡二叉树

平衡二叉树（Balanced BinaryTree）又被称为AVL树。它具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。

平衡二叉树一般是一个有序树，它具有二叉树的所有性质，其遍历操作和二叉树的遍历操作相同。但是由于其对二叉树施加了额外限制，因而其添加、删除操作都必须保证平衡二叉树的性子被保持。

平衡二叉树中引入了一个概念：平衡二叉树节点的平衡因子，它指的是该节点的两个子树，即左子树和右子树的高度差，即用左子树的高度减去右子树的高度，如果该节点的某个子树不存在，则该子树的高度为0,如果高度差的绝对值超过1就要根据情况进行调整。

代码

这里借助上一篇二叉树深度中计算二叉树深度的代码来计算左子树和右子树的高度差。

[java] view plain copy
  1. static class TreeNode {  
  2.     int val;  
  3.     TreeNode left;  
  4.     TreeNode right;  
  5.   
  6.     public TreeNode(int val) {  
  7.         this.val = val;  
  8.     }  
  9. }  
  10.   
  11. public static boolean isBalanced(TreeNode root) {  
  12.     if (root == null) {  
  13.         return true;  
  14.     }  
  15.     if (root.left == null && root.right == null) {  
  16.         return true;  
  17.     }  
  18.     // 计算得到左子树的深度  
  19.     int leftDepth = treeDepth(root.left);  
  20.     // 计算得到右子树的深度  
  21.     int rightDepth = treeDepth(root.right);  
  22.     // 如果高度差大于1，不满足平衡二叉的条件  
  23.     if (Math.abs(leftDepth - rightDepth) > 1) {  
  24.         return false;  
  25.     }  
  26.     // 判断左子树和右子树是否满足平衡二叉树的条件  
  27.     return isBalanced(root.left) && isBalanced(root.right);  
  28. }  
  29.   
  30. private static int treeDepth(TreeNode root) {  
  31.     if (root == null) {  
  32.         return 0;  
  33.     }  
  34.     // 计算左子树的深度  
  35.     int left = treeDepth(root.left);  
  36.     // 计算右子树的深度  
  37.     int right = treeDepth(root.right);  
  38.     // 树root的深度=路径最长的子树深度 + 1  
  39.     return left >= right ? (left + 1) : (right + 1);  
  40. }