[236] Lowest Common Ancestor of a Binary Tree

果然還是看解答省事 Orz 我真是沒有天份 Orz

大概只有想到一半！ （有感覺到XD）長在不同邊的話是return root ，

長在同一邊是return 上面那個node，但是寫不粗乃  XD！

原來是！！！left 跟right 都要去找，如果各有找到東西，表示他們在不同邊，return root。

不然的話，一定會有一個人先找到而被return，另一個人因為在它下面可是已經被return 掉了，

因此另一個一定會是NULL。（找不到）

所以當兩者在同一邊時，回傳有被找到的那一個就可以了。

（為什麼別人這麼聰明啊 QQ）

/**

* Definition for a binary tree node.

* struct TreeNode {

* int val;

* struct TreeNode *left;

* struct TreeNode *right;

* };

*/

struct TreeNode* findFirst(struct TreeNode* root, struct TreeNode* p, struct TreeNode* q) {

struct TreeNode *ret1, *ret2;

if (root == NULL)

return NULL;

if (root == p || root == q)

return root;

ret1 = findFirst(root->left, p,q);

ret2 = findFirst(root->right, p,q);

if (ret1 && ret2) //both children return a node(長在左右) means root is the LCA

return root;

return (ret1==NULL)? ret2:ret1;

}

struct TreeNode* lowestCommonAncestor(struct TreeNode* root, struct TreeNode* p, struct TreeNode* q) {

return findFirst(root, p,q);

}