【题目】
Given a binary tree, determine if it is height-balanced.
For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees ofeverynode never differ by more than 1.
【分析】
无
【代码】
/*********************************
* 日期:2014-12-24
* 作者:SJF0115
* 题目: 110.Balanced Binary Tree
* 来源:https://oj.leetcode.com/problems/balanced-binary-tree/
* 结果:AC
* 来源:LeetCode
* 总结:
**********************************/
#include <iostream>
#include <algorithm>
using namespace std;
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
class Solution {
public:
bool isBalanced(TreeNode *root) {
if(balancedHeight(root) == -1){
return false;
}
else{
return true;
}//if
}
private:
// 如果是平衡二叉树返回该二叉树的高度
// 否则返回-1
int balancedHeight(TreeNode *node){
if(node == NULL){
return 0;
}//if
// 左子树高度
int left = balancedHeight(node->left);
// 右子树高度
int right = balancedHeight(node->right);
// 左右子树高度差不超过1
if(abs(left - right) > 1 || left < 0 || right < 0){
// -1代表不满足平衡二叉树要求
return -1;
}//if
return max(left,right)+1;
}
};
//按先序序列创建二叉树
int CreateBTree(TreeNode*& T){
int data;
//按先序次序输入二叉树中结点的值,-1表示空树
cin>>data;
if(data == -1){
T = NULL;
}
else{
T = new TreeNode(data);
//构造左子树
CreateBTree(T->left);
//构造右子树
CreateBTree(T->right);
}
return 0;
}
int main() {
Solution solution;
TreeNode* root(0);
CreateBTree(root);
cout<<solution.isBalanced(root);
}
【复杂度】
时间复杂度 O(n),空间复杂度 O(logn)
分享到:
相关推荐
leetcode的题目:Balanced Binary Tree
* [Binary Search Tree](https://github.com/kamyu104/LeetCode#binary-search-tree) * [Breadth-First Search](https://github.com/kamyu104/LeetCode#breadth-first-search) * [Depth-First Search]...
leetcode 答案leetcode-java leetcode.com 的 Java 答案 ================索引================ com.leetcode.array Search a ...com.leetcode.list ...Balanced Binary Tree Maximum Depth of Binary Tree Same Tree
leetcode 和 oj 力码下载器 您已接受的提交的下载器 依赖 只需运行pip install -r requirements.txt来安装它们 ...balanced-binary-tree │ └── Solution.660938.java ├── best-time-to-buy-and-sell-stock
leetcode旋转 Leetcode 视频链接待补充:triangular_flag: 打卡 题目类型 题目编号 ...Balanced Binary Tree Leetcode #110 Day6 AVL Tree Leetcode #108 Day7 AVL Tree Rotation 补充AVL Tree旋转操作
左程云leetcode 数据结构和算法学习笔记 一、简介 1. 2. 3. 4. 5. 6. 二、数据结构 1. 二维数组(Array2D) 位数组(Bit Set) 静态数组(Fixed Size Array) 有序表(Ordered Array) 2. 队列(Queues) (后进先出...
Balanced Binary Tree Flatten Binary Tree to Linked List Populating Next Right Pointers in Each Node II 二叉树的构建 Construct Binary Tree from Preorder and Inorder Traversal Construct Binary Tree from...
左程云leetcode 数据结构和算法学习笔记 一、简介 1. 2. 3. 4. 5. 6. 二、数据结构 1. 二维数组(Array2D) 位数组(Bit Set) 静态数组(Fixed Size Array) 有序表(Ordered Array) 2. 队列(Queues) (后进先出...
leetcode 分类 LeetCode Progress 128/154 Other Solutions C++,有详细思路解释 python,部分有解释 Java,部分有解释 ...norvig神牛Python代码写的很飘逸,果然是有LISP内功的人!...Balanced Binary Tree Binar
leetcode 和 oj 完整的面试准备文档 - 基于 GooglePrep.txt 推荐书籍 编程面试曝光:找到下一份工作的秘密,John Mongan、Eric Giguere、Noah Suojanen、Noah Kindler、John Wiley & Sons 算法导论,Thomas H. ...
1.5 二叉树是否平衡Given a binary tree, determine if it is height-balanced.For this prob
balanced binary search tree - 对于给定的初始值,自动生成平衡二叉搜索树。 [] 算法 BFS JS实现2 Leetcode问题解决 问题 洪水填充问题(已解决):油漆问题。 给定一个由矩阵表示的图像,绘制一个像素 (src) 和...
leetcode lintcode差异 Lintcode 解题思路记录 Table of Contents Linked List Convert Sorted List to Binary Search Tree Given a singly linked list where elements are sorted in ascending order, convert it ...
算法与计算机科学 这个软件库的算法,数据结构,其实现的集合,解决了400多个从流行编码的挑战网站如对问题 , , , , , , , 以及一些在面试中会问很多人的面试问题。 算法是用Java实现的。...