首页 > 代码库 > 判断一棵二叉树是不是平衡二叉树

判断一棵二叉树是不是平衡二叉树

2024-07-04 23:38:19   228人阅读

二叉树中任意左右子树的深度相差不超过1，那么它就是一棵平衡二叉树。

两种解法。

第一种：菜鸟的解法，出现重复遍历，时间复杂度高。

 1 bool IsBalanced(BinaryTreeNode* root)
 2 {
 3     if (root == NULL)
 4     {
 5         return true ;
 6     }
 7     int left = TreeDepth(root->m_pLeft);//该函数实现见我上一篇博客“数的深度”
 8     int right = TreeDepth(root->m_pRight);
 9     if ((left - right) > 1 || (left - right) < -1)
10     {
11         return false ;
12     }
13     else
14         return IsBalanced(root->m_pLeft) && IsBalanced(root->m_pRight);
15 }

第二种：大神的解法，只遍历一次，高端大气上档次。

 1 bool IsBalanced2(BinaryTreeNode* root , int& Depth)
 2 {
 3     if (root == NULL)
 4     {
 5         Depth = 0 ;
 6         return true ;
 7     }
 8     int left , right ;
 9     if (IsBalanced2(root->m_pLeft, left) && IsBalanced2(root->m_pRight, right))
10     {
11         int diff = left - right ;
12         if (diff <= 1 && diff >= -1)
13         {
14             Depth = 1 + (left > right ? left : right );
15             return true ;
16         }
17     }
18 
19     return false ;
20 
21 }
22 bool IsBalanced2(BinaryTreeNode* root)
23 {
24     int Depth = 0 ;
25     return IsBalanced2(root , Depth);
26 }

 


联系
我们