【第三轮】7.7-7.13 CareerCup 4.1

【解题思路】
Compute the height of each sub-tree while checking whether the sub-tree is balanced or not


【时间复杂度】
O(n) (n is the number of nodes)

【空间复杂度】
O(h) (h is the height of tree)


【gist link】
https://gist.github.com/happyWinner/ab96e6406d587547756c

【解题思路】
recursion method. each time we compute length(b->lchild) and length(b->rchild). But in this way, we compute length duplicately. Runtime is O(n^2), space is O(H), H is tree height.
To optimize it, we can check balance in length computating.
【时间复杂度】
O(n)
【空间复杂度】
O(H)
【gist link】
https://gist.github.com/qianhuang/6abaee1a1c8599edca97

方法一：
【解题思路】
递归，写一个计算节点 height 的函数
【时间复杂度】
O (N log (N)) -- N : 总节点数
【空间复杂度】
O( ? )
【gist link】
https://gist.github.com/JoyceeLee/5a6141e1afb69bcd3295

方法二：
【解题思路】
在 getHeight 里同时进行 balance 检查
【时间复杂度】
O (N) -- N : 总节点数
【空间复杂度】
O( H )
【gist link】
https://gist.github.com/JoyceeLee/5a6141e1afb69bcd3295

【解题思路】 recursive solutions. check if left subtree balanced, if right subtree balanced and if the height difference is less than one.    return the height and use -1 to indicate the subtree is not balanced.
【时间复杂度】
O(N)
【空间复杂度】
O(H)
【gist link】https://gist.github.com/jyhjuzi/99e67e68e726427da58c

【解题思路】
Compute the height of the two subtree while comparing if the subtree is balanced or not. return -1 for height to indicate not balanced.
【时间复杂度】
O(N)
【空间复杂度】
O(H)
【gist link】
https://gist.github.com/iwilbert/bb5372cf358ff1981548

【解题思路】
参考了答案的思路，一起检查height和balance，自己智商捉鸡了...
【时间复杂度】
O(N)
【空间复杂度】
O(H)
【gist link】
https://gist.github.com/Noahsark/da4873bb3831d8ea8c65

【解题思路】height() + check()
【时间复杂度】
O (n)
【空间复杂度】
O(h)
【gist link】
https://gist.github.com/xun-gong/ce771c4af3f039a35bef

leetcode也有一样的 Balanced Binary Tree，想了老半天DFS啥啥什么顺序啥啥，结果重点应该在checkBalanced的时候一旦不balance就返回-1
【解题思路】参考了书上的答案，getHeight and check ifBalanced at the same time
【时间复杂度】
O (n)
【空间复杂度】
O(lgN)
【gist link】
https://gist.github.com/XiaoxiaoLi/c013c43b64b602be0013