判断二叉树是不平衡树 代码(C)

本文地址: http://blog.csdn.net/caroline_wendy

题目: 输入一颗二叉树的根结点, 判断该树是不是平衡二叉树.

二叉平衡树: 任意结点的左右子树的深度相差不超过1.

使用后序遍历的方式, 并且保存左右子树的深度, 进行比较.

代码:

/*
 * main.cpp
 *
 *  Created on: 2014.6.12
 *      Author: Spike
 */

/*eclipse cdt, gcc 4.8.1*/

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

struct BinaryTreeNode {
	int m_nValue;
	BinaryTreeNode* m_pLeft;
	BinaryTreeNode* m_pRight;
};

bool IsBalanced(BinaryTreeNode* pRoot, int* pDepth) {
	if (pRoot == NULL) {
		*pDepth = 0;
		return true;
	}
	int left, right;
	if (IsBalanced(pRoot->m_pLeft, &left) && IsBalanced(pRoot->m_pRight, &right)) {
		int diff = left - right;
		if (diff>=-1 && diff<=1) {
			*pDepth = 1 + (left>right?left:right);
			return true;
		}
	}
	return false;
}

bool IsBalanced(BinaryTreeNode* pRoot) {
	int depth = 0;
	return IsBalanced(pRoot, &depth);
}

BinaryTreeNode* init(void) {
	BinaryTreeNode* pRoot = new BinaryTreeNode(); pRoot->m_nValue = http://www.mamicode.com/1;>
输出:
result = true