【第三轮】7.14-7.20 CareerCup 4.7

4.7 Design an algorithm and write code to find the first common ancestor of two nodes in a binary tree. Avoid storing additional nodes in a data structure. NOTE: This is not necessarily a binary search tree.

回复解法可以按照以下格式来

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

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

【解题思路】Assumption: when p is one ancestor of q's, we say p is the first common ancestor of p, q
                  Recursion to solve this problem
                      Case 1: p, q locate in different side of root, first common ancestor must be root
                      Case 2: p, q locates in same side of root
                                 sub-case-1: p,q both in left of root , focus on left subtree and recurse on it
                                 sub-case-2: p,q both in right of root, focus on right subtree and recurse on it
                      判断p, q 在不在某subtree也用到了recursion，做的时候没想到，看了答案才知道的
                      整道题就是逻辑＋递归，代码量很少，想着费脑
【时间复杂度】O(n)
【空间复杂度】O(h)
【gist link】https://gist.github.com/xun-gong/05fcd99c19eb6b6b1e85

【解题思路】
recursion

【时间复杂度】
O(n)
【空间复杂度】
O(h)
【gist link】
https://github.com/donnice/donni ... f40876c5374f77c35dc
【Test】
                      5                                                               
               2                  8                              
         1          4       7                                          
               3         6   

【解题思路】
Recursion

【时间复杂度】
O(N^2) in worst case

【空间复杂度】
O(Height of N) for call stack

【gist link】
https://gist.github.com/chrislukkk/307199f6879e2faa05da
Helper class: https://gist.github.com/chrislukkk/2a1f825b8e924ea773e8

【解题思路】
recursion


【时间复杂度】
O(n)

【空间复杂度】
O(h)

【gist link】
https://gist.github.com/happyWinner/58853a40c12679d44fb2

【解题思路】
recursion 测试是否包含两个节点，然后再确定是 root 还是 其子结点
【时间复杂度】
O(n)
【空间复杂度】
O(？)
【gist link】
https://gist.github.com/JoyceeLee/765c93b3f1c130fc5501

【解题思路】find a chain p,q on same side. 书里的
(1)p,q are on left side, branch left to look for common ancestor
(2)p,q are on right side, branch right to look for common ancestor
(3)p,q are no longer on same side, find first common ancestor
【时间复杂度】o(n)
【空间复杂度】o(n)
【gist link】https://gist.github.com/hilda8519/fe8866902dc1705e7899

【解题思路】recursion
if root is null, return null
if root is q/p, return root
if, p,q in different sides, return root
if p,q in the same side, check that side to see if p,q on different sides
【时间复杂度】o(n)
【空间复杂度】o(n)
【gist link】https://gist.github.com/happyWinner/58853a40c12679d44fb2

【解题思路】recursion
first check if the tree covers both the two nodes, if not, return false
recursive function:
1. if contains node1 only, return node1
2. if contains node2 only, return node2
3. if contains both, return the first ancestor
【时间复杂度】o(n)
【空间复杂度】o(H) for recursion calls
【gist link】https://gist.github.com/jyhjuzi/f3f546249eb93d3adb7b

【解题思路】recursion
first check if the tree covers both the two nodes, if not, return false
recursive function:
1. if contains node1 only, return node1
2. if contains node2 only, return node2
3. if contains both, return the first ancestor
【时间复杂度】o(n)
【空间复杂度】o(H) for recursion calls
【gist link】https://gist.github.com/jyhjuzi/f3f546249eb93d3adb7b