【第三轮】7.14-7.20 CareerCup 4.7

【解题思路】
Recursion. If one node has the situation: both left and right sub-tree contains one of our nodes, then this is the ancestor we find.

【时间复杂度】
O(n)
【空间复杂度】
O(h)
【gist link】
https://gist.github.com/Noahsark/4847851df110e9819316

【解题思路】Recursion, check how many nodes are found in current node and subtrees, if it's 2, then the current node is the ancestor. Return this node.
【时间复杂度】O(n)
【空间复杂度】O(h)
【gist link】https://gist.github.com/nealhu/d9824c0c3907b8a2c54f

【解题思路】
return null pointer if either of the two nodes doesn't exist in the tree; return current root if either node (or both) equal(s) the root; return current root if two nodes belong to different branches; recursively solve for common ancestor if both nodes belong to the same side.
【时间复杂度】
O(N)
【空间复杂度】
O(H)
【gist link】
https://gist.github.com/88b9c5c5179390ca53d4
【test case】
binary search tree: 8 || 3 10 || 1 6 14 || 4 7 13
Common ancester of 3 and 3 is 3
Common ancester of 3 and 6 is 3
Common ancester of 1 and 4 is 3
Common ancester of 6 and 10 is 8
Common ancester of 10 and 13 is 10
Press any key to continue . . .

【解题思路】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

【解题思路】
check if p and q  do exist in the tree first. then recursively check if p is on the left side, and if q is on the left side.
(1) p and q on the different side of the tree, root is the answer
(2) p and q on left side of the tree, find left subtree
(3) p and q on right side of the tree, find right subtree
【时间复杂度】
O(N)
【空间复杂度】
O(N)
【gist link】
https://gist.github.com/iwilbert/66236a13a579b9c117d4