【第四轮】6.28 - 7.4 Career Cup 4.1

4.1  Implement a function to check if a binary tree is balanced. For the purposes of this question, a balanced tree is defined to be a tree such that the heights of the two subtrees of any node never differ by more than one.

【解题思路】
【时间复杂度】
【空间复杂度】
【gist link】
【test case】(optional，如果觉得比较好，欢迎贴出来分享）

Notice：
1、记得在程序注释中表明自己算法的时间、空间复杂度
2、代码难懂之处加注释
3、每道题目有对应的帖子，除了贴解法，欢迎探讨各种follow up questions，集思广益
4、任何未尽之处，欢迎回报名帖提问，我会进一步作出修改

【解题思路】分治法：分别判断左右子树是否是平衡二叉树，如果不是直接返回-1，如果是返回子树的高度。
【时间复杂度】
O(N)，N是节点的个数。
【空间复杂度】
O(1)，只用到了额外的常数空间
【gist link】
https://gist.github.com/iFighting/e2cc0f35f820545d979f
【test case】(optional，如果觉得比较好，欢迎贴出来分享）

第一次地里发，无比激动

[解题思路] dfs: 一遍dfs扫描，判断左右子树是否是balanced，如果是则更新高度为左右子树高度最大值加1，否则false;
[时间复杂度]
O(n), n个节点
[空间复杂度]
O(1)用来存储高度的变量
[github link]
https://github.com/lidongmeng/CC150/blob/master/4.1.cpp

【解题思路】divide & conquer
【时间复杂度】
O(n), n为节点的个数。
【空间复杂度】
O(h), h为树的高度。
【gist link】
https://gist.github.com/zhangxin0804/ffa98b09481a1a9c22c1
【test case】(optional，如果觉得比较好，欢迎贴出来分享）

【解题思路】
对每一个节点比对左树和右树高度，如果高度差大于阈值则不是平衡树
【时间复杂度】
O(n^2)
【空间复杂度】
O(n)
【gist link】
https://gist.github.com/alikewmk ... 1-checkbalance-java