数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究C++ 程序检查树是否为平衡树
假设我们有一个二叉树，我们需要检查其高度是否平衡。我们知道，对于一个高度平衡的树，树中每个节点的左子树高度和右子树高度的绝对差为 0 或 1。
所以，如果输入如下所示：
则输出为 True
为了解决这个问题，我们将遵循以下步骤：
定义一个函数 dfs()，它将接收节点作为参数。
如果节点为空，则：
返回 0
l := 1 + dfs(节点的左子节点)
r := 1 + dfs(节点的右子节点)
如果 |l - r| > 1，则：
ret := false
返回 l 和 r 中的最大值
在主方法中执行以下操作：
ret := true
dfs(根节点)
返回 ret
让我们看看下面的实现来更好地理解：
示例
#include <bits/stdc++.h>
using namespace std;
class TreeNode {
public:
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
class Solution {
public:
bool ret;
int dfs(TreeNode* node){
if(!node)
return 0;
int l = 1 + dfs(node->left);
int r = 1 + dfs(node->right);
if(abs(l - r) > 1)
ret = false;
return max(l, r);
}
bool isBalanced(TreeNode* root) {
ret = true;
dfs(root);
return ret;
}
};
main(){
Solution ob;
TreeNode *root = new TreeNode(25);
root->left = new TreeNode(19);
root->right = new TreeNode(4);
root->left->left = new TreeNode(9);
root->left->right = new TreeNode(7);
cout << (ob.isBalanced(root));
}输入
TreeNode *root = new TreeNode(25); root->left = new TreeNode(19); root->right = new TreeNode(4); root->left->left = new TreeNode(9); root->left->right = new TreeNode(7);
输出
1
更新于: 2020年10月8日
501 次浏览
广告