RobbEr's Blog

Welcome

例题-平衡二叉树

发表于 更新于 分类于 阅读次数： Valine：
本文字数： 829 阅读时长 ≈ 1 分钟

题目描述

输入一棵二叉树，判断该二叉树是否是平衡二叉树。

在这里，我们只需要考虑其平衡性，不需要考虑其是不是排序二叉树
平衡二叉树（Balanced Binary Tree），具有以下性质：
它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。

原理

由平衡二叉树的原理可得出只需要计算出每个结点的左子树与右子树深度即可判断。即可用dfs搜索出根结点的左子树和右子树分别的度，在进行比较即可判断。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class TreeNode {
public:
	int data;
	TreeNode* lchild = nullptr;
	TreeNode* rchild = nullptr;
	TreeNode(int data) :data(data) {};
	~TreeNode() {};
};

class Tree {
public:
	int deep(TreeNode* root) 
	{	//深度计算
	    if (root == nullptr)
		    return 0;
    	int l = 0, r = 0;
    	l = deep(root->lchild);
    	r = deep(root->rchild);
    	return l > r ? l + 1 : r + 1;
	}
	bool IsBalanced_Solution(TreeNode* pRoot) 
	{	//是否为平衡二叉树
    	if (pRoot == nullptr)
    		return true;
    	int left = deep(pRoot->lchild);
    	int right = deep(pRoot->rchild);
    	if (abs(left - right) <= 1)
    		return true;
    	else
    		return false;
	}
};

输入为

1
[5,3,7,2,4,8,6]

输出为

1
true