【第三轮】7.7-7.13 CareerCup 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】
---------------Optional，如果觉得test case比较好，欢迎写出来分享----------------------
【test case】

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

【解题思路】
递归遍历每一个点，计算左右两个subtree的高度差
【时间复杂度】
O(N)
【空间复杂度】
O(N)
【gist link】
https://gist.github.com/chouclee/dac2df817f826f5df3a4
---------------OPTional，如果觉得test case比较好，欢迎写出来分享----------------------
【test case】    /*                            7
                         *                         /    \
                         *                     /         \
                         *                  4            9
                         *                 / \         / \
                         *              2   5     8   10
                         *            / \    \            \
                         *         1   3    6          11
                         *        /
                        *       0
                 */  




补充内容 (2014-7-9 12:54):
gist link贴错了。。。囧 https://gist.github.com/chouclee/5a7bdbed1ab1c8b3d150

【解题思路】
参考了网上的思路，用递归遍历每一个点，并计算其左右树的高度差。凡是有超过1的就说明不平衡
【时间复杂度】
O(N)
【空间复杂度】
O(N)
【gist link】
https://github.com/donnice/donnice/blob/master/Q4_1
【Test】
例子里我用的树分别是：
              5                                                                7
            2                  8                                            2                     8
      1          4       7                                          1             4      
            3                                                                3            5

【解题思路】
Recursion.

自己写的时候return了一个boolean值(表示subtree是否balance)和int值(height of the subtree)
书上的答案return -1如果subtree is not balance， 省下了boolean的空间

【时间复杂度】
O(N) - N is # of tree nodes

【空间复杂度】
O(N)

【gist link】
https://gist.github.com/chrislukkk/6581e137e1ad9673a973
BinaryTree: https://gist.github.com/chrislukkk/2a1f825b8e924ea773e8

【test case】
A binary tree builder: Building a tree based on itspreorder and inorder sequence
https://gist.github.com/chrislukkk/2a1f825b8e924ea773e8

【解题思路】
参考书后解答=。=
【时间复杂度】
O(N)
【空间复杂度】
O(H)
【gist link】
https://gist.github.com/e448a924ba7d3b4d0f8b
【test case】
BST:
5 3 4 1 2 6  -> false
5 3 4 1 2 6 8 -> true
5 3 4 1 2 6 8 1 -> false

【解题思路】Ref to the book... count the left height and right height of each node, also copy the tree structure from lss
【时间复杂度】
O(N)
【空间复杂度】
O(N)
【gist link】
https://gist.github.com/bitcpf/26394ee53639cdbf721f

【解题思路】Return the current height for helper() function. Return -1 if the tree is not balanced.
【时间复杂度】O(N)
【空间复杂度】O(H)
【gist link】https://gist.github.com/jason51122/ec57311f8d1fcd8e9e41

【解题思路】recurse through the entire tree, compute the height of each subtree
【时间复杂度】o(n^2)
【空间复杂度】o(n)
【gist link】https://gist.github.com/hilda8519/24a6435951a05ac1b8de

答案的第二个例子不错

【解题思路】transverse the tree recursively, examine each node and check if two subtrees are balanced.
【时间复杂度】o(n)
【空间复杂度】o(max(height))
【gist link】https://gist.github.com/nealhu/091a742d6c11d5298760