【算法】判断二叉树是否是平衡二叉树

迈不过友情╰ 2022-08-09 05:08 236阅读 0赞

**问题**：判断一个二叉树是否是平衡二叉树。

**分析**：平衡二叉树要求左子树和右子树的高度相差为1，且左右子树都是平衡二叉树。递归可以很好的解决这个问题。但是首先要求树的深度。

**代码实现**：

typedef struct tree
    {
    	int data;
    	struct tree* lchild,*rchild;
    }BTree;
    int get_tree_depth(BTree* t)
    {
    	if (t == NULL){
    		return 0;
    	}
    	int ldepth,rdepth,depth;
    	ldepth = get_tree_depth(t->lchild) + 1;
    	rdepth = get_tree_depth(t->rchild) + 1;
    	depth = ldepth>rdepth? ldepth:rdepth;
    	return depth;
    }
    
    bool is_balance_tree(BTree* t)
    {
    	int lchildDepth,rchildDepth;
    	if (t == NULL || (!t->rchild && !t->rchild)) // t为null或没有子树
    	{
    		return true;
    	}
    	lchildDepth = get_tree_depth(t->lchild);
    	rchildDepth = get_tree_depth(t->rchild);
    	if (abs(lchildDepth-rchildDepth) <= 1)
    		return is_balance_tree(t->lchild) && is_balance_tree(t->rchild);
    	else
    		return false;
    }

**测试代码**：

int main()
    {
    	BTree* root = NULL;
    	createtree(&root); //ABD#E##FG###C##
    	cout << "get_tree_depth:" << get_tree_depth(root) << endl;
    
    	cout <<"is_balance_tree:" << is_balance_tree(root) << endl;
    
    	system("pause");
    	return 0;
    }

void createtree(BTree** bt){
    	char ch;
    	scanf("%c",&ch);
    	if (ch == '#')
    	{
    		*bt = NULL;
    	}
    	else
    	{
    		*bt = (BTree*)malloc(sizeof(BTree));
    		(*bt)->data = ch;
    		createtree(&(*bt)->lchild);
    		createtree(&(*bt)->rchild);
    	}
    }

问题：这里有个问题就是，每次递归的时候都求一遍depth，有办法解决吗？