本文概述

• C++
• C
• Java
• Python3
• C#
• C++
• C
• Java
• Python3
• C#

一棵树, 没有叶子比其他叶子离根更远。不同的平衡方案允许对” 更远的距离” 进行不同的定义, 并进行不同的工作量以保持平衡。
考虑一种高度平衡方案, 其中应检查以下条件以确定二叉树是否平衡。
一棵空树是高度平衡的。如果满足以下条件, 则非空二叉树T是平衡的：
1)T的左子树是平衡的
2)T的右子树是平衡的
3)左子树和右子树的高度之差不大于1。
【如何确定二叉树是否高度平衡（）】上面的高度平衡方案用于AVL树中。下图显示了两棵树, 其中一棵是高度平衡的, 而另一棵则不是。第二棵树没有高度平衡, 因为左子树的高度比右子树的高度大2。

文章图片
要检查树是否高度平衡, 请获取左右子树的高度。如果高度差不超过1并且左右子树是平衡的, 则返回true, 否则返回false。
C++

/* CPP program to check if a tree is height-balanced or not */ #include < bits/stdc++.h> using namespace std; /* A binary tree node has data, pointer to left child and a pointer to right child */ class node { public : int data; node* left; node* right; }; /* Returns the height of a binary tree */ int height(node* node); /* Returns true if binary tree with root as root is height-balanced */ bool isBalanced(node* root) { int lh; /* for height of left subtree */ int rh; /* for height of right subtree *//* If tree is empty then return true */ if (root == NULL) return 1; /* Get the height of left and right sub trees */ lh = height(root-> left); rh = height(root-> right); if ( abs (lh - rh) < = 1 & & isBalanced(root-> left) & & isBalanced(root-> right)) return 1; /* If we reach here then tree is not height-balanced */ return 0; }/* UTILITY FUNCTIONS TO TEST isBalanced() FUNCTION *//* returns maximum of two integers */ int max( int a, int b) { return (a> = b) ? a : b; }/* The function Compute the "height" of a tree. Height is the number of nodes along the longest path from the root node down to the farthest leaf node.*/ int height(node* node) { /* base case tree is empty */ if (node == NULL) return 0; /* If tree is not empty then height = 1 + max of left height and right heights */ return 1 + max(height(node-> left), height(node-> right)); }/* Helper function that allocates a new node with the given data and NULL left and right pointers. */ node* newNode( int data) { node* Node = new node(); Node-> data = http://www.srcmini.com/data; Node-> left = NULL; Node-> right = NULL; return (Node); }//Driver code int main() { node* root = newNode(1); root-> left = newNode(2); root-> right = newNode(3); root-> left-> left = newNode(4); root-> left-> right = newNode(5); root-> left-> left-> left = newNode(8); if (isBalanced(root)) cout < <"Tree is balanced" ; else cout < < "Tree is not balanced" ; return 0; }//This code is contributed by rathbhupendra

C

/* C program to check if a tree is height-balanced or not */ #include < stdio.h> #include < stdlib.h> #define bool int/* A binary tree node has data, pointer to left child and a pointer to right child */ struct node { int data; struct node* left; struct node* right; }; /* Returns the height of a binary tree */ int height( struct node* node); /* Returns true if binary tree with root as root is height-balanced */ bool isBalanced( struct node* root) { int lh; /* for height of left subtree */ int rh; /* for height of right subtree *//* If tree is empty then return true */ if (root == NULL) return 1; /* Get the height of left and right sub trees */ lh = height(root-> left); rh = height(root-> right); if ( abs (lh - rh) < = 1 & & isBalanced(root-> left) & & isBalanced(root-> right)) return 1; /* If we reach here then tree is not height-balanced */ return 0; }/* UTILITY FUNCTIONS TO TEST isBalanced() FUNCTION *//* returns maximum of two integers */ int max( int a, int b) { return (a> = b) ? a : b; }/*The function Compute the "height" of a tree. Height is the number of nodes along the longest path from the root node down to the farthest leaf node.*/ int height( struct node* node) { /* base case tree is empty */ if (node == NULL) return 0; /* If tree is not empty then height = 1 + max of left height and right heights */ return 1 + max(height(node-> left), height(node-> right)); }/* Helper function that allocates a new node with the given data and NULL left and right pointers. */ struct node* newNode( int data) { struct node* node = ( struct node*) malloc ( sizeof ( struct node)); node-> data = http://www.srcmini.com/data; node-> left = NULL; node-> right = NULL; return (node); }int main() { struct node* root = newNode(1); root-> left = newNode(2); root-> right = newNode(3); root-> left-> left = newNode(4); root-> left-> right = newNode(5); root-> left-> left-> left = newNode(8); if (isBalanced(root)) printf ("Tree is balanced" ); else printf ( "Tree is not balanced" ); getchar (); return 0; }

Java

/* Java program to determine if binary tree is height balanced or not *//* A binary tree node has data, pointer to left child, and a pointer to right child */ class Node { int data; Node left, right; Node( int d) { data = http://www.srcmini.com/d; left = right = null ; } }class BinaryTree { Node root; /* Returns true if binary tree with root as root is height-balanced */ boolean isBalanced(Node node) { int lh; /* for height of left subtree */int rh; /* for height of right subtree *//* If tree is empty then return true */ if (node == null ) return true ; /* Get the height of left and right sub trees */ lh = height(node.left); rh = height(node.right); if (Math.abs(lh - rh) < = 1 & & isBalanced(node.left) & & isBalanced(node.right)) return true ; /* If we reach here then tree is not height-balanced */ return false ; }/* UTILITY FUNCTIONS TO TEST isBalanced() FUNCTION */ /*The function Compute the"height" of a tree. Height is the number of nodes along the longest path from the root node down to the farthest leaf node.*/ int height(Node node) { /* base case tree is empty */ if (node == null ) return 0 ; /* If tree is not empty then height = 1 + max of left height and right heights */ return 1 + Math.max(height(node.left), height(node.right)); }public static void main(String args[]) { BinaryTree tree = new BinaryTree(); tree.root = new Node( 1 ); tree.root.left = new Node( 2 ); tree.root.right = new Node( 3 ); tree.root.left.left = new Node( 4 ); tree.root.left.right = new Node( 5 ); tree.root.left.left.left = new Node( 8 ); if (tree.isBalanced(tree.root)) System.out.println( "Tree is balanced" ); else System.out.println( "Tree is not balanced" ); } }//This code has been contributed by Mayank Jaiswal(mayank_24)

Python3

""" Python3 program to check if a tree is height-balanced """ # A binary tree Nodeclass Node: # Constructor to create a new Node def __init__( self , data): self .data = http://www.srcmini.com/data self .left = None self .right = None# function to find height of binary tree def height(root):# base condition when binary tree is empty if root is None : return 0 return max (height(root.left), height(root.right)) + 1# function to check if tree is height-balanced or not def isBalanced(root):# Base condition if root is None : return True# for left and right subtree height lh = height(root.left) rh = height(root.right)# allowed values for (lh - rh) are 1, -1, 0 if ( abs (lh - rh) < = 1 ) and isBalanced( root.left) is True and isBalanced( root.right) is True : return True# if we reach here means tree is not # height-balanced tree return False# Driver function to test the above function root = Node( 1 ) root.left = Node( 2 ) root.right = Node( 3 ) root.left.left = Node( 4 ) root.left.right = Node( 5 ) root.left.left.left = Node( 8 ) if isBalanced(root): print ("Tree is balanced" ) else : print ( "Tree is not balanced" )# This code is contributed by Shweta Singh

C#

using System; /* C# program to determine if binary tree is height balanced or not *//* A binary tree node has data, pointer to left child, and a pointer to right child */ public class Node { public int data; public Node left, right; public Node( int d) { data = http://www.srcmini.com/d; left = right = null ; } }public class BinaryTree { public Node root; /* Returns true if binary tree with root as root is height-balanced */ public virtual bool isBalanced(Node node) { int lh; //for height of left subtreeint rh; //for height of right subtree/* If tree is empty then return true */ if (node == null ) { return true ; }/* Get the height of left and right sub trees */ lh = height(node.left); rh = height(node.right); if (Math.Abs(lh - rh) < = 1 & & isBalanced(node.left) & & isBalanced(node.right)) { return true ; }/* If we reach here then tree is not height-balanced */ return false ; }/* UTILITY FUNCTIONS TO TEST isBalanced() FUNCTION */ /* The function Compute the"height" of a tree. Height is the number of nodes along the longest path from the root node down to the farthest leaf node.*/ public virtual int height(Node node) { /* base case tree is empty */ if (node == null ) { return 0; }/* If tree is not empty then height = 1 + max of left height and right heights */ return 1 + Math.Max(height(node.left), height(node.right)); }public static void Main( string [] args) { BinaryTree tree = new BinaryTree(); tree.root = new Node(1); tree.root.left = new Node(2); tree.root.right = new Node(3); tree.root.left.left = new Node(4); tree.root.left.right = new Node(5); tree.root.left.left.left = new Node(8); if (tree.isBalanced(tree.root)) { Console.WriteLine( "Tree is balanced" ); } else { Console.WriteLine( "Tree is not balanced" ); } } }//This code is contributed by Shrikant13

输出如下：

Tree is not balanced

时间复杂度：O(n ^ 2)最坏的情况发生在树倾斜的情况下。
优化的实现：
可以通过在相同的递归中计算高度而不是单独调用height()函数来优化上述实现。感谢Amar建议这个优化版本。这种优化将时间复杂度降低到O(n)。
C++

/* C++ program to check if a tree is height-balanced or not */ #include < bits/stdc++.h> using namespace std; #define bool int/* A binary tree node has data, pointer to left child and a pointer to right child */ class node { public : int data; node* left; node* right; }; /* The function returns true if root is balanced else false The second parameter is to store the height of tree. Initially, we need to pass a pointer to a location with value as 0. We can also write a wrapper over this function */ bool isBalanced(node* root, int * height) {/* lh --> Height of left subtree rh --> Height of right subtree */ int lh = 0, rh = 0; /* l will be true if left subtree is balanced and r will be true if right subtree is balanced */ int l = 0, r = 0; if (root == NULL) { *height = 0; return 1; }/* Get the heights of left and right subtrees in lh and rh And store the returned values in l and r */ l = isBalanced(root-> left, & lh); r = isBalanced(root-> right, & rh); /* Height of current node is max of heights of left and right subtrees plus 1*/ *height = (lh> rh ? lh : rh) + 1; /* If difference between heights of left and right subtrees is more than 2 then this node is not balanced so return 0 */ if ( abs (lh - rh)> = 2) return 0; /* If this node is balanced and left and right subtrees are balanced then return true */ else return l & & r; }/* UTILITY FUNCTIONS TO TEST isBalanced() FUNCTION *//* Helper function that allocates a new node with the given data and NULL left and right pointers. */ node* newNode( int data) { node* Node = new node(); Node-> data = http://www.srcmini.com/data; Node-> left = NULL; Node-> right = NULL; return (Node); }//Driver code int main() { int height = 0; /* Constructed binary tree is 1 / 2 3 / / 4 5 6 / 7 */ node* root = newNode(1); root-> left = newNode(2); root-> right = newNode(3); root-> left-> left = newNode(4); root-> left-> right = newNode(5); root-> right-> left = newNode(6); root-> left-> left-> left = newNode(7); if (isBalanced(root, & height)) cout < <"Tree is balanced" ; else cout < < "Tree is not balanced" ; return 0; }//This is code is contributed by rathbhupendra

C

/* C program to check if a tree is height-balanced or not */ #include < stdio.h> #include < stdlib.h> #define bool int/* A binary tree node has data, pointer to left child and a pointer to right child */ struct node { int data; struct node* left; struct node* right; }; /* The function returns true if root is balanced else false The second parameter is to store the height of tree. Initially, we need to pass a pointer to a location with value as 0. We can also write a wrapper over this function */ bool isBalanced( struct node* root, int * height) { /* lh --> Height of left subtree rh --> Height of right subtree */ int lh = 0, rh = 0; /* l will be true if left subtree is balanced and r will be true if right subtree is balanced */ int l = 0, r = 0; if (root == NULL) { *height = 0; return 1; }/* Get the heights of left and right subtrees in lh and rh And store the returned values in l and r */ l = isBalanced(root-> left, & lh); r = isBalanced(root-> right, & rh); /* Height of current node is max of heights of left and right subtrees plus 1*/ *height = (lh> rh ? lh : rh) + 1; /* If difference between heights of left and right subtrees is more than 2 then this node is not balanced so return 0 */ if ( abs (lh - rh)> = 2) return 0; /* If this node is balanced and left and right subtrees are balanced then return true */ else return l & & r; }/* UTILITY FUNCTIONS TO TEST isBalanced() FUNCTION *//* Helper function that allocates a new node with the given data and NULL left and right pointers. */ struct node* newNode( int data) { struct node* node = ( struct node*) malloc ( sizeof ( struct node)); node-> data = http://www.srcmini.com/data; node-> left = NULL; node-> right = NULL; return (node); }//Driver code int main() { int height = 0; /* Constructed binary tree is 1 / 23 / / 456 / 7 */ struct node* root = newNode(1); root-> left = newNode(2); root-> right = newNode(3); root-> left-> left = newNode(4); root-> left-> right = newNode(5); root-> right-> left = newNode(6); root-> left-> left-> left = newNode(7); if (isBalanced(root, & height)) printf ("Tree is balanced" ); else printf ( "Tree is not balanced" ); getchar (); return 0; }

Java

/* Java program to determine if binary tree is height balanced or not *//* A binary tree node has data, pointer to left child, and a pointer to right child */ class Node {int data; Node left, right; Node( int d) { data = http://www.srcmini.com/d; left = right = null ; } }//A wrapper class used to modify height across //recursive calls. class Height { int height = 0 ; }class BinaryTree {Node root; /* Returns true if binary tree with root as root is height-balanced */ boolean isBalanced(Node root, Height height) { /* If tree is empty then return true */ if (root == null ) { height.height = 0 ; return true ; }/* Get heights of left and right sub trees */ Height lheight = new Height(), rheight = new Height(); boolean l = isBalanced(root.left, lheight); boolean r = isBalanced(root.right, rheight); int lh = lheight.height, rh = rheight.height; /* Height of current node is max of heights of left and right subtrees plus 1*/ height.height = (lh> rh ? lh : rh) + 1 ; /* If difference between heights of left and right subtrees is more than 2 then this node is not balanced so return 0 */ if (Math.abs(lh - rh)> = 2 ) return false ; /* If this node is balanced and left and right subtrees are balanced then return true */ else return l & & r; }public static void main(String args[]) { Height height = new Height(); /* Constructed binary tree is 1 / 23 / / 456 / 7*/ BinaryTree tree = new BinaryTree(); tree.root = new Node( 1 ); tree.root.left = new Node( 2 ); tree.root.right = new Node( 3 ); tree.root.left.left = new Node( 4 ); tree.root.left.right = new Node( 5 ); tree.root.right.right = new Node( 6 ); tree.root.left.left.left = new Node( 7 ); if (tree.isBalanced(tree.root, height)) System.out.println("Tree is balanced" ); else System.out.println( "Tree is not balanced" ); } }//This code has been contributed by Mayank Jaiswal(mayank_24)

Python3

""" Python3 program to check if Binary tree is height-balanced """# A binary tree node class Node:# constructor to create node of # binary tree def __init__( self , data): self .data = http://www.srcmini.com/data self .left = self .right = None# utility class to pass height object class Height: def __init__( self ): self .height = 0# helper function to check if binary # tree is height balanced def isBalanced(root):# lh and rh to store height of # left and right subtree lh = Height() rh = Height()# Base condition when tree is # empty return true if root is None : return True# l and r are used to check if left # and right subtree are balanced l = isBalanced(root.left) r = isBalanced(root.right)# height of tree is maximum of # left subtree height and # right subtree height plus 1if abs (lh.height - rh.height) < = 1 : return l and r# if we reach here then the tree # is not balanced return False# Driver function to test the above function""" Constructed binary tree is 1 /\ 23 /\ / 4 5 6 /7 """ # to store the height of tree during traversalroot = Node( 1 ) root.left = Node( 2 ) root.right = Node( 3 ) root.left.left = Node( 4 ) root.left.right = Node( 5 ) root.right.left = Node( 6 ) root.left.left.left = Node( 7 )if isBalanced(root): print ( 'Tree is balanced' ) else : print ( 'Tree is not balanced' )# This code is contributed by Shweta Singh

C#

using System; /* C# program to determine if binary tree is height balanced or not *//* A binary tree node has data, pointer to left child, and a pointer to right child */ public class Node {public int data; public Node left, right; public Node( int d) { data = http://www.srcmini.com/d; left = right = null ; } }//A wrapper class used to modify height across //recursive calls. public class Height { public int height = 0; }public class BinaryTree {public Node root; /* Returns true if binary tree with root as root is height-balanced */ public virtual bool isBalanced(Node root, Height height) { /* If tree is empty then return true */ if (root == null ) { height.height = 0; return true ; }/* Get heights of left and right sub trees */ Height lheight = new Height(), rheight = new Height(); bool l = isBalanced(root.left, lheight); bool r = isBalanced(root.right, rheight); int lh = lheight.height, rh = rheight.height; /* Height of current node is max of heights of left and right subtrees plus 1*/ height.height = (lh> rh ? lh : rh) + 1; /* If difference between heights of left and right subtrees is more than 2 then this node is not balanced so return 0 */ if (Math.Abs(lh - rh)> = 2) { return false ; }/* If this node is balanced and left and right subtrees are balanced then return true */ else { return l & & r; } }/*The function Compute the"height" of a tree. Height is the number of nodes along the longest path from the root node down to the farthest leaf node.*/ public virtual int height(Node node) { /* base case tree is empty */ if (node == null ) { return 0; }/* If tree is not empty then height = 1 + max of left height and right heights */ return 1 + Math.Max(height(node.left), height(node.right)); }public static void Main( string [] args) { Height height = new Height(); /* Constructed binary tree is 1 /\ 23 / \/ 456 / 7*/ BinaryTree tree = new BinaryTree(); tree.root = new Node(1); tree.root.left = new Node(2); tree.root.right = new Node(3); tree.root.left.left = new Node(4); tree.root.left.right = new Node(5); tree.root.right.right = new Node(6); tree.root.left.left.left = new Node(7); if (tree.isBalanced(tree.root, height)) { Console.WriteLine( "Tree is balanced" ); } else { Console.WriteLine( "Tree is not balanced" ); } } }//This code is contributed by Shrikant13

输出如下

Tree is balanced

时间复杂度：O(n)
如果你发现上述任何代码/算法不正确, 或者找到其他解决相同问题的方法, 请写评论。

推荐阅读

• 

  需求分析方法,什么是一种面向数据流的需求分析方法
• 

  小学学霸冲a卷二年级上册数学试卷 二年级上册数学试卷可打印
• 

  疫情期间,大家都用的什么牌子的口罩呀？求推荐？
• 

  在美国大片中,一个人黑进国家安全网窃取机密,几分钟后FBI找上门来,现实中可能吗？
• 

  羽毛球反手接杀慢动作 羽毛球如何接杀教学视频，羽毛球如何接杀挑后场
• 

  cad怎么输入角度符号详细介绍
• 

  php星星塔
• 

  简单好玩的C语言编程代码，很6很好玩的短小c语言程序
• 

  兰州水上巴士现在还开吗今天 兰州水上巴士现在还开吗
• 

  平面制图作品分析,平面广告设计作品分析
• 

  二类银行卡能改一类吗
• 

  柳暗花名又一村的前一句 柳暗花名又一村原文及翻译
• 

  深海鱼可以生吃吗
• 

  广告正文分析,广告分析案例
• 

  【给木木的信】2018/09|【给木木的信】2018/09 决定
• 

  棕榈叶的功效与作用 药用价值
• 

  资助卡是什么卡
• 

  白芍的功效与作用及食用方法禁忌 白芍的功效与作用及食用方法禁忌
• 

  阿司匹林|阿司匹林肠溶片能和降压药在早上一起服吗？有哪些注意事项？
• 

  蛋挞液的牛奶可以用水代替吗

• 如何开发基于云的SaaS应用程序（）
• 如何设计一个很小的URL或URL缩短器（）
• 如何声明一个指向函数的指针（）
• 如何在C#中创建线程（解析和详细代码）
• 如何在C#中创建ArrayList（用法示例）
• 如何使用Kotlin在Android Studio中创建项目（）
• 如何在Google AMP中创建Floating amp-addthis（）
• 如何在Tableau中创建故事（）
• 10个查找和删除重复文件的工具