平衡二叉树的性质为: 要么是一棵空树，要么任何一个节点的左右子树高度差的绝对值不超过 1。给定一棵二叉树（保证树中的节点值互不相同），判断这棵二叉树是否为平衡二叉树。
一颗树的高度指的是树的根节点到所有节点的距离中的最大值。
[编程题]判断二叉树是否为平衡二叉树
- 热度指数：1807 时间限制：C/C++ 2秒，其他语言4秒 空间限制：C/C++ 256M，其他语言512M
- 算法知识视频讲解
输入描述:
第一行输入两个整数 n 和 root，n 表示二叉树的总节点个数，root 表示二叉树的根节点。
以下 n 行每行三个整数 fa，lch，rch，表示 fa 的左儿子为 lch，右儿子为 rch。(如果 lch 为 0 则表示 fa 没有左儿子，rch同理)
输出描述:
如果是平衡二叉树则输出 "true"，否则输出 "false"。
示例1
输入
3 1 1 2 3 2 0 0 3 0 0
输出
true
示例2
输入
6 1 1 2 3 2 4 5 4 6 0 3 0 0 5 0 0 6 0 0
输出
false
备注:
这个题应该提示一下节点是怎么输入的，给的示例太小看不出来是层次还是先序，踩了好久的坑才测出来输入的是先序序列。利用递归的方式构建二叉树，然后递归计算子树高度来判断平衡性就可以了，注意任意子树的左右子树高度之差都不能超过1。
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.Queue;
import java.util.LinkedList;
class TreeNode {
public int val;
public TreeNode left;
public TreeNode right;
public TreeNode(int val) {
this.val = val;
this.left = null;
this.right = null;
}
}
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] params = br.readLine().trim().split(" ");
int n = Integer.parseInt(params[0]);
// 先建树
TreeNode tree = buildTree(br);
// 然后判断平衡性
System.out.println(isBalanced(tree));
}
private static TreeNode buildTree(BufferedReader br) throws IOException {
String line = br.readLine();
int[] arr = cast(line);
TreeNode head = new TreeNode(arr[0]);
if(arr[1] != 0)
head.left = buildTree(br);
if(arr[2] != 0)
head.right = buildTree(br);
return head;
}
private static int[] cast(String str){
String[] strings = str.split(" ");
int[] arr = new int[strings.length];
for(int i = 0; i < arr.length; i++)
arr[i] = Integer.parseInt(strings[i]);
return arr;
}
private static boolean isBalanced(TreeNode root) {
if(root == null) return true; // 空树平衡
if(Math.abs(TreeDepth(root.left) - TreeDepth(root.right)) <= 1)
return isBalanced(root.left) && isBalanced(root.right); // 左右子树都要平衡
return false;
}
private static int TreeDepth(TreeNode tree) {
if(tree == null){
return 0;
}else
return Math.max(TreeDepth(tree.left), TreeDepth(tree.right)) + 1;
}
}
编辑于 2021-06-13 11:02:45
回复(1)
import java.util.Scanner;
public class Main {
public static Node[] nodes;
public static int n;
public static int root;
public static class Node {
public int val;
public int left, right;
Node(int val, int left , int right) {
this.val = val;
this.left = left;
this.right = right;
}
}
public static class ReturnVal {
public boolean isBalance;
public int height;
ReturnVal(boolean isBalance, int height) {
this.isBalance = isBalance;
this.height = height;
}
}
public static ReturnVal isBalance(int index) {
if (index == 0) {
return new ReturnVal(true, 0);
}
ReturnVal left = isBalance(nodes[index].left);
if (!left.isBalance) return new ReturnVal(false, 0);
ReturnVal right = isBalance(nodes[index].right);
if (!right.isBalance) return new ReturnVal(false, 0);
if (Math.abs(left.height-right.height) > 1) return new ReturnVal(false, 0);
int height = Math.max(left.height, right.height) + 1;
boolean isBalance = Math.abs(left.height-right.height) <= 1 && left.isBalance & right.isBalance;
return new ReturnVal(isBalance, height);
}
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
n = input.nextInt();
root = input.nextInt();
nodes = new Node[n+1];
for (int i = 0; i < n; i++) {
int val = input.nextInt();
int left = input.nextInt();
int right = input.nextInt();
nodes[val] = new Node(val, left, right);
}
System.out.println(isBalance(root).isBalance);
}
}
发表于 2020-08-05 17:12:46
回复(0)
#include <bits/stdc++.h>
using namespace std;
struct TreeNode{
int val;
TreeNode* lch;
TreeNode* rch;
TreeNode(int x):val(x),lch(NULL),rch(NULL){}
};
void createTree(TreeNode* root, int& cnt){
if(cnt == 0) return;
int p, l, r;
cin >> p >> l >> r;
if(l){
TreeNode* lch = new TreeNode(l);
root->lch = lch;
createTree(root->lch, --cnt);
}
if(r){
TreeNode* rch = new TreeNode(r);
root->rch = rch;
createTree(root->rch, --cnt);
}
return;
}
int helper(TreeNode* root){
if(!root) return 0;
int leftHight = helper(root->lch);
int rightHight = helper(root->rch);
if(leftHight == -1 || rightHight == -1)
return -1;
if(abs(leftHight - rightHight) < 2)
return max(leftHight, rightHight)+1;
else
return -1;
}
bool judge(TreeNode* root){
if(helper(root) == -1)
return false;
else
return true;
}
int main(){
int n, root_val;
cin >> n >> root_val;
TreeNode* root = new TreeNode(root_val);
createTree(root, n);
if(judge(root))
cout << "true" << endl;
else
cout << "false" << endl;
return 0;
}
发表于 2020-05-07 11:26:29
回复(0)
题目描述是不是有问题？
以下 n 行每行三个整数 fa，lch，rch，表示 fa 的左儿子为 lch，右儿子为 rch。(如果 lch 为 0 则表示 fa 没有左儿子，rch同理)
发表于 2019-08-27 16:10:59
回复(1)
#include <iostream>
#include <math.h>
using namespace std;
struct TreeNode{
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x): val(x), left(NULL), right(NULL) {}
};
void createTree(TreeNode* root, int& n) {
if(n == 0)
return ;
int rootval, leftval, rightval;
cin >> rootval >> leftval >> rightval;
if(leftval != 0) {
TreeNode* leftNode = new TreeNode(leftval);
leftNode->left = leftNode->right = nullptr;
root->left = leftNode;
createTree(leftNode, --n);
}
if(rightval != 0) {
TreeNode* rightNode = new TreeNode(rightval);
rightNode->left = rightNode->right = nullptr;
root->right = rightNode;
createTree(rightNode, --n);
}
return ;
}
int getHeight(TreeNode* root) {
if(root == nullptr)
return 0;
int leftHeight = getHeight(root->left);
int rightHeight = getHeight(root->right);
int treeHeight = max(leftHeight, rightHeight) + 1;
return treeHeight;
}
bool isBalanced(TreeNode* root) {
if(root == nullptr)
return true;
return isBalanced(root->left) && isBalanced(root->right) && abs(getHeight(root->left) - getHeight(root->right)) <= 1;
}
int main() {
int n, rootval;
cin >> n >> rootval;
TreeNode* root = new TreeNode(rootval);
root->left = root->right = nullptr;
createTree(root, n);
if(isBalanced(root))
cout << "true" << endl;
else
cout << "false" << endl;
return 0;
}
发表于 2022-06-09 15:10:20
回复(0)
#include <map>
#include <vector>
#include <unordered_map>
#include <iostream>
#include <memory>
using namespace std;
struct TreeNode
{
TreeNode(int value) : _value(value){
}
std::shared_ptr<TreeNode> _left; //左子树
std::shared_ptr<TreeNode> _right;//右子树
int _value;
};
// 获取缓存的节点，或者构造一个节点
std::shared_ptr<TreeNode> find_or_make_item(std::map<int, std::shared_ptr<TreeNode>>& value_node_map, int value)
{
std::shared_ptr<TreeNode> item;
if (value_node_map.find(value) == value_node_map.end()) {
item = std::make_shared<TreeNode>(value);
value_node_map[value] = item;
}
else {
item = value_node_map[value];
}
return item;
}
// 计算节点深度
int treeDepth(std::shared_ptr<TreeNode> tree)
{
if (tree == nullptr) {
return 0;
}
return max(treeDepth(tree->_left), treeDepth(tree->_right)) + 1;
}
// 判断是否是平衡二叉树
bool isBalanced(std::shared_ptr<TreeNode> root) {
if (root == nullptr) {
return true;
}
// 任何一个节点的左右子树高度差的绝对值不超过 1
if (abs(treeDepth(root->_left) - treeDepth(root->_right)) <= 1) {
return isBalanced(root->_left) && isBalanced(root->_right); // 左右子树都要平衡
}
return false;
}
int main()
{
int n = 0;
int value_root = 0;
while (cin >> n >> value_root) {
// 题目并没有说按照什么顺序输入节点，所以需要用map保存已输入的节点
std::map<int, std::shared_ptr<TreeNode>> value_node_map;
for (int i = 0; i < n; ++i) {
int value = 0;
int left = 0;
int right = 0;
cin >> value >> left >> right;
//当前节点
std::shared_ptr<TreeNode> item = find_or_make_item(value_node_map, value);
//左节点
if (left != 0) {
std::shared_ptr<TreeNode> item_left = find_or_make_item(value_node_map, left);
item->_left = item_left;
}
//右节点
if (right != 0) {
std::shared_ptr<TreeNode> item_right = find_or_make_item(value_node_map, right);
item->_right = item_right;
}
}
//根节点
std::shared_ptr<TreeNode> root = value_node_map[value_root];
if (isBalanced(root))
cout << "true" << endl;
else
cout << "false" << endl;
}
return 0;
}
#include <vector>
#include <unordered_map>
#include <iostream>
#include <memory>
using namespace std;
struct TreeNode
{
TreeNode(int value) : _value(value){
}
std::shared_ptr<TreeNode> _left; //左子树
std::shared_ptr<TreeNode> _right;//右子树
int _value;
};
// 获取缓存的节点，或者构造一个节点
std::shared_ptr<TreeNode> find_or_make_item(std::map<int, std::shared_ptr<TreeNode>>& value_node_map, int value)
{
std::shared_ptr<TreeNode> item;
if (value_node_map.find(value) == value_node_map.end()) {
item = std::make_shared<TreeNode>(value);
value_node_map[value] = item;
}
else {
item = value_node_map[value];
}
return item;
}
// 计算节点深度
int treeDepth(std::shared_ptr<TreeNode> tree)
{
if (tree == nullptr) {
return 0;
}
return max(treeDepth(tree->_left), treeDepth(tree->_right)) + 1;
}
// 判断是否是平衡二叉树
bool isBalanced(std::shared_ptr<TreeNode> root) {
if (root == nullptr) {
return true;
}
// 任何一个节点的左右子树高度差的绝对值不超过 1
if (abs(treeDepth(root->_left) - treeDepth(root->_right)) <= 1) {
return isBalanced(root->_left) && isBalanced(root->_right); // 左右子树都要平衡
}
return false;
}
int main()
{
int n = 0;
int value_root = 0;
while (cin >> n >> value_root) {
// 题目并没有说按照什么顺序输入节点，所以需要用map保存已输入的节点
std::map<int, std::shared_ptr<TreeNode>> value_node_map;
for (int i = 0; i < n; ++i) {
int value = 0;
int left = 0;
int right = 0;
cin >> value >> left >> right;
//当前节点
std::shared_ptr<TreeNode> item = find_or_make_item(value_node_map, value);
//左节点
if (left != 0) {
std::shared_ptr<TreeNode> item_left = find_or_make_item(value_node_map, left);
item->_left = item_left;
}
//右节点
if (right != 0) {
std::shared_ptr<TreeNode> item_right = find_or_make_item(value_node_map, right);
item->_right = item_right;
}
}
//根节点
std::shared_ptr<TreeNode> root = value_node_map[value_root];
if (isBalanced(root))
cout << "true" << endl;
else
cout << "false" << endl;
}
return 0;
}
发表于 2021-11-17 18:08:32
回复(0)
#include <stdio.h>
#include <stdlib.h>
typedef int Id;
typedef struct {
Id id;
Id l_child, r_child;
} TreeNodeInfo, *INFO;
typedef struct TreeNode {
Id id;
struct TreeNode* left;
struct TreeNode* right;
} TreeNode, *PTNode, *BT;
BT CreateBT(INFO infos, Id root_id) {
// recursion exit condition
if (!root_id) return NULL;
BT t = (PTNode) malloc(sizeof(TreeNode));
if (!t) return NULL;
t->id = root_id;
t->left = CreateBT(infos, infos[root_id].l_child);
t->right = CreateBT(infos, infos[root_id].r_child);
return t;
}
int isBalanced(BT t, int* ans) {
if (!t) return 0;
int l = isBalanced(t->left, ans);
int r = isBalanced(t->right, ans);
if (abs(l - r) > 1) *ans = 0;
return 1 + fmax(l, r);
}
int main(const int argc, const char* const argv[]) {
int n, root_id;
fscanf(stdin, "%d %d", &n, &root_id);
TreeNodeInfo infos[n + 1];
Id fa, l_ch, r_ch;
while (n--) {
fscanf(stdin, "%d %d %d", &fa, &l_ch, &r_ch);
infos[fa].id = fa;
infos[fa].l_child = l_ch;
infos[fa].r_child = r_ch;
}
int ans = 1;
isBalanced(CreateBT(infos, root_id), &ans);
fputs(ans ? "true" : "false", stdout);
return 0;
}
发表于 2021-08-03 19:44:54
回复(0)
#判断以root为根节点的树nodes是否是平衡树
def is_balance(root, nodes):
#如果树为空
#树高为0
#是平衡树
if root == 0:
return 0, True
#如果树不为空
#分别求左右树高
#判断左右子树是否为平衡树
l_h, l_B = is_balance(nodes[root]["l"], nodes)
r_h, r_B = is_balance(nodes[root]["r"], nodes)
#接下来判断以root为根的树是否为平衡树
#先假设不是
is_B = False
#求树高
rt_h = max(l_h, r_h) + 1
#如果左右子树是平衡树
if l_B and r_B:
#根据平衡树的定义判断
if abs(l_h - r_h) <= 1:
is_B = True
return rt_h, is_B
#树的总节点数,根
n, root = map(int,input().strip().split(' '))
#树
tree={}
for i in range(n):
root,l,r=map(int,input().strip().split(' '))
tree[root]={"l":l,"r":r}
_, is_B = is_balance(root, tree)
if is_B:
print("true")
else:
print("false") 树的题目注意利用递归。
发表于 2021-06-30 10:26:27
回复(0)
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct TreeNode{
int lch;
int rch;
};
struct ReturnType{
bool flag;
int height;
};
ReturnType isBalanced(const vector<TreeNode> &v, int head){
if(head == 0){
return {true, 0};
}
ReturnType left = isBalanced(v, v[head].lch);
ReturnType right = isBalanced(v, v[head].rch);
int height = max(left.height, right.height) + 1;
bool flag = left.flag && right.flag && abs(left.height - right.height) < 2;
return {flag, height};
}
int main(void){
int n, root;
cin >> n;
cin >> root;
vector<TreeNode> v(n + 1);
int cur;
for(int i = 0; i < n; i++){
cin >> cur;
cin >> v[cur].lch;
cin >> v[cur].rch;
}
ReturnType res = isBalanced(v, root);
if(res.flag)
cout << "true" << endl;
else
cout << "false" << endl;
return 0;
#include <vector>
#include <algorithm>
using namespace std;
struct TreeNode{
int lch;
int rch;
};
struct ReturnType{
bool flag;
int height;
};
ReturnType isBalanced(const vector<TreeNode> &v, int head){
if(head == 0){
return {true, 0};
}
ReturnType left = isBalanced(v, v[head].lch);
ReturnType right = isBalanced(v, v[head].rch);
int height = max(left.height, right.height) + 1;
bool flag = left.flag && right.flag && abs(left.height - right.height) < 2;
return {flag, height};
}
int main(void){
int n, root;
cin >> n;
cin >> root;
vector<TreeNode> v(n + 1);
int cur;
for(int i = 0; i < n; i++){
cin >> cur;
cin >> v[cur].lch;
cin >> v[cur].rch;
}
ReturnType res = isBalanced(v, root);
if(res.flag)
cout << "true" << endl;
else
cout << "false" << endl;
return 0;
}
使用二叉树套路来解题
先获取左边二叉树信息:: 平衡吗？height?
在获取右边二叉树信息：平衡吗？height?
综合左右子树信息：abs(left->height - right->height) < 2?
发表于 2021-05-19 10:31:17
回复(0)
#include<iostream>
using namespace std;
struct TreeNode{
int val;
TreeNode* left;
TreeNode* right;
};
void CreateTree(TreeNode* pRoot,int& n){
if(n==0){
return;
}
int rootval,leftval,rightval;
cin>>rootval>>leftval>>rightval;
if(leftval!=0){
TreeNode* leftnode = new TreeNode;
leftnode->val = leftval;
leftnode->left=leftnode->right=nullptr;
pRoot->left = leftnode;
CreateTree(leftnode,--n);
}
if(rightval!=0){
TreeNode* rightnode = new TreeNode;
rightnode->val = rightval;
rightnode->left=rightnode->right=nullptr;
pRoot->right = rightnode;
CreateTree(rightnode,--n);
}
}
struct ReturnType{
bool isbalanced;
int height;
ReturnType(bool _isbalanced,int _height){
isbalanced = _isbalanced;
height = _height;
}
};
ReturnType process(TreeNode* pRoot){
if(pRoot==nullptr){
ReturnType a(true,0);
return a;
}
ReturnType leftData = process(pRoot->left);
ReturnType rightData = process(pRoot->right);
bool isbalanced =leftData.isbalanced && rightData.isbalanced &&(abs(leftData.height-rightData.height)<2);
int height = max(leftData.height,rightData.height)+1;
ReturnType res(isbalanced,height);
return res;
}
int main(){
int n,rootval;
cin>>n>>rootval;
TreeNode* pRoot = new TreeNode;
pRoot->val = rootval;
pRoot->left = pRoot->right = nullptr;
TreeNode* pCurrNode = pRoot;
CreateTree(pCurrNode,n);
ReturnType res = process(pRoot);
if(res.isbalanced){
cout<<"true"<<endl;
}else{
cout<<"false"<<endl;
}
return 0;
}
发表于 2020-07-29 16:06:45
回复(0)
#include<bits/stdc++.h>
using namespace std;
// 法一
int getHeight(int root,int* lc,int* rc)
{
if(!root) return 0;
return 1 + max(getHeight(lc[root],lc,rc),getHeight(rc[root],lc,rc));
}
bool judge(int root,int*lc, int* rc)
{
if(!root) return true;
int l = getHeight(lc[root],lc,rc);
int r = getHeight(rc[root],lc,rc);
if(abs(l-r)>=2) return false;
return true;
}
bool visit(int root,int* lc,int* rc)
{
if(!root) return true;
return judge(root,lc,rc) && visit(lc[root],lc,rc) && visit(rc[root],lc,rc);
}
///// 改进，法二 树形dp
// 需要子树返回的信息
// 是否平衡 以及树高
struct ReturnType{
bool isBalanced;
int height;
ReturnType(bool a,int b):isBalanced(a),height(b){}
};
ReturnType process(int root,int* lc,int* rc)
{
// 空树是平衡树
if(!root) return ReturnType(true,0);
ReturnType l = process(lc[root],lc,rc);
ReturnType r = process(rc[root],lc,rc);
int cur_height = max(l.height,r.height) + 1;
// 以当前结点为根的树平衡的条件：左右子树都平衡 且 左右子树的树高差值最多为1
bool cur_balance = l.isBalanced && r.isBalanced && abs(l.height-r.height)<2 ? true : false;
return ReturnType(cur_balance,cur_height);
}
int main()
{
int n,root;
cin>>n>>root;
int* lc = new int[n+1];
int* rc = new int[n+1];
int p;
for(int i=0;i<n;++i)
{
cin>>p;
cin>>lc[p]>>rc[p];
}
//if(visit(root,lc,rc))
if(process(root,lc,rc).isBalanced)
cout<<"true";
else cout<<"false";
return 0;
}
发表于 2020-02-06 12:13:59
回复(2)
我也是服了，代码在leetcode上能过，在牛客上就过不了？
int isBalanceTree(TreeNode *root) {
if (root == nullptr) return 0; // 判断边界
int leftHeight = isBalanceTree(root->left);
int rightHeight = isBalanceTree(root->right);
if (leftHeight == -1 || rightHeight == -1)
return -1;
if (abs(leftHeight - rightHeight) < 2)
return max(leftHeight, rightHeight) + 1;
else
return -1;
}
bool isBalanced(TreeNode* root) {
if (isBalanceTree(root) != -1) {
return true;
} else
return false;
}
发表于 2020-01-17 18:37:35
回复(1)
问题信息
通过挑战的用户
查看代码-
2022-08-29 16:10:01 -
2022-08-18 10:43:43
-
2022-08-18 08:30:33 -
2022-08-17 18:52:19
-
2022-07-25 11:35:48
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K2座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
