1077: 平衡二叉树的判定

解法：

平衡二叉树是一种特殊的二叉树，它满足以下两个条件：

1. 左子树和右子树的高度差不超过1（即，左右子树高度差的绝对值不超过1）。
2. 左子树和右子树都是平衡二叉树。

后序遍历过程中每次判断左右子树高度差和1的关系即可

#include<iostream>
using namespace std;
struct treeNode {char val;treeNode* left, * right;treeNode(char x) :val(x), left(NULL), right(NULL) {};
};
treeNode* buildtree() {char ch;cin >> ch;if (ch == '#') return NULL;treeNode* root = new treeNode(ch);root->left = buildtree();root->right = buildtree();return root;
}
bool f = false;
int dfs(treeNode* r) {if (r == NULL) return 0;int lh = dfs(r->left);int rh = dfs(r->right);if (abs(lh - rh) > 1) f = true;return max(lh, rh) + 1;
}
int  main() {treeNode* root = buildtree();if (root == NULL) cout << "yes!";else {dfs(root);if (f) cout << "no!";else cout << "yes!";}return 0;
}