1077: 平衡二叉树的判定

本文主要是介绍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;
}

这篇关于1077: 平衡二叉树的判定的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---