判断二叉树是否平衡 java

Love The Way You Lie 2022-07-16 20:15 185阅读 0赞

实现一个函数，检查二叉树是否平衡。

二叉树平衡的定义如下：任意一个结点，其两颗子树的高度差不超过1

递归访问每个整棵树，计算每个结点子树的高度

**\[java\]**  [view plain][]   [copy][view plain]

1.  **public** **class** BTreeBalanced \{  
2.      **static** **class** TreeNode \{  
3.          **int** data;  
4.          **static** TreeNode left;  
5.          **static** TreeNode right;  
6.      \}  
7.      **public** **static** **boolean** isBalanced(TreeNode root) \{  
8.          **if** (**null** == root) **return** **true**;  
9.          **int** heightDiff = getHeight(root.left) - getHeight(root.right);  
10.         **if** ( Math.abs(heightDiff)  > 1 ) \{  
11.             **return** **false**;  
12.         \}  
13.         **else** \{  
14.             **return** ( isBalanced(TreeNode.left) && isBalanced(TreeNode.right) );  
15.         \}  
16.     \}  
17.     **public** **static** **int** getHeight(TreeNode root) \{  
18.         **if** (**null** == root) **return** 0;  
19.         **return** Math.max( getHeight(root.left), getHeight(root.right) + 1 );  
20.     \}  
21. \}

但这样做的效率不高，getHeight（）会被反复调用计算同一个结点的高度，时间复杂度为O（N logN）

getHeight（）其实不仅可以检查高度，还能检查树是否平衡，只要将判断左右子树高度差是否大于一放进getHeight（）就可以了，下面用checkHeight（）来表示这一段代码。

这样做的好处是时间复杂度降低了，为O（N）,空间复杂度为O（H），H为树的高度

**\[java\]**  [view plain][]   [copy][view plain]

1.  **public** **static** **int** checkHeight(TreeNode root) \{  
2.          **if** (**null** == root) **return** 0;  
3.          **int** leftHeight = checkHeight(root.left);  
4.          **if** ( leftHeight == -1 ) \{  
5.              **return** -1; //unbalanced  
6.          \}  
7.            
8.          **int** rightHeight = checHeight(root.right);  
9.          **if** ( rightHeight == -1 ) \{  
10.             **return** -1; //unbalanced  
11.         \}  
12.           
13.         **int** heightDiff = leftHeight - rightHeight;  
14.         **if** (Math.abs(heightDiff) > 1) \{  
15.             **return** -1; // unbalanced  
16.         \}  
17.         **else** \{  
18.             **return** Math.max( rightHeight, rightHeight + 1 );  
19.         \}  
20.     \}  
21.     **public** **static** **boolean** isBalanced2(TreeNode root) \{  
22.         **if**(checkHeight(root) == -1) \{  
23.             **return** **false**;  
24.         \}  
25.         **else** \{  
26.             **return** **true**;  
27.         \}  
28.     \}  
29.

[view plain]: http://blog.csdn.net/michellechouu/article/details/46873829#