【数据结构】中判断一棵树是否为平衡二叉树

朱雀 2022-06-11 01:09 126阅读 0赞

平衡二叉树：就是指这棵二叉树的左子树和右子树之间的差值不大于1。

先定义一个二叉树的结构体：

struct TreeNode
    {
    	TreeNode* _left;
    	TreeNode* _right;
    };

在判断一颗二叉树是否为平衡二叉树的时候：

第一种方法是，先计算出这棵二叉树的高度。

计算高度的时候使用递归的方法，递归到左子树和右子树。

int TreeDepth(TreeNode* _root)//使用递归方法求出二叉树的高度
    {
    	if (_root == NULL)
    	{
    		return 0;
    	}
    	int left = TreeDepth(_root->_left);
    	int right = TreeDepth(_root->_right);
    	return (left > right) ? (left + 1) : (right + 1);
    }

再使用判断平衡的函数，计算如果左子树和右子树的差值小于1就是平衡二叉树。

bool IsBalanceTree(TreeNode* _root)
    {
    	if (_root == NULL)//空树也是平衡二叉树
    	{
    		return true;
    	}
    	int left = TreeDepth(_root->_left);//
    	int right = TreeDepth(_root->_right);
    	if ((left - right) > 1 || (left - right) < -1)//平衡二叉树的判断条件，左子树与右子树的高度差不大于1
    	{
    		//如果高度差的绝对值大于1，返回错误
    		return false;
    	}
    	else
    	{
    		return IsBalanceTree(_root->_left) && IsBalanceTree(_root->_right);
    	}
    }

但是这种方法需要遍历两遍，时间复杂度较高。

下面使用第二种方法，只需要遍历一遍，可以将高度和是否为平衡二叉树判断出来。

bool IsBalanceTree(TreeNode* _root, int &Depth)
    {
    	if (_root == NULL)
    	{
    		Depth = 0;
    		return true;
    	}
    	int left, right;
    	if (IsBalanceTree(_root->_left, left) && IsBalanceTree(_root->_right, right))
    	{
    		int diff = left - right;//定义一个数值等于左边减去右边
    		if (diff < 1 && diff >= -1)
    		{
    			Depth = 1 + (left>right ? left : right);
    			return true;
    		}
    	}
    	return false;
    }