建立一颗二叉树并判断是否为平衡二叉树

#include
using namespace std;

//定义节点
typedef struct node
{
	struct node* left;
	struct node* right;
	char  data;
}BiTreeNode, * BiTree;


//按照前序顺序建立二叉树
void createBiTree(BiTree& T)
{//输入需要将二叉树补成满二叉树 如AB##C## 
	char c;
	cin >> c;
	if (c == "#")           
		T = NULL;
	else
	{
		T = new BiTreeNode;
		T->data = c;
		createBiTree(T->left);
		createBiTree(T->right);
	}
}
class Solution {
public:
    void isBalanced(BiTreeNode* root) {
        int height = dfs(root);
        if (height >= 0) cout<< "是平衡二叉树";
        else  cout << "不是平衡二叉树"; 
    }

    // 当非平衡时，return -1; 平衡时，return high;
    // 首先判断左子树平衡与否，再判断右子树平衡与否，在判断整棵树平衡与否；
    int dfs(BiTreeNode* root) {
        if (!root) return 0;//root等于0时，该节点符合要求，返回其深度0，而不返回-1；
        int left = dfs(root->left); //left最开始的取值为0，从底朝上遍历，先左子树，后右子树，最后根节点
        if (left < 0) return -1;//若出现节点深度小于0，则进行剪枝，开始向上返回，之后的迭代不再进行
        int right = dfs(root->right);
        if (right < 0) return -1;
        if (abs(left - right) > 1) return -1;
        return max(left, right) + 1;//返回树的最大深度.
    }
};

int main()
{
	BiTree T;               //声明一个指向二叉树根节点的指针               
	createBiTree(T);
    cout << "二叉树创建完成！" << endl;
    cout << endl;
    Solution s;
    s.isBalanced(T);
    s.dfs(T);
	return 0;
}