Lowest Common Ancestor.png
解題思路 ：
LCA 的第一題 沒有 parent pointer 所以回 true 的條件為
1.root = A or root = B
2.root 左邊跟 root 右邊都檢查出有 A 或著 B 存在 (即 Ａ, B 在 root 兩邊)
C++ code :
<pre><code>
class Solution {
public:
/**
* @param root: The root of the binary search tree.
* @param A and B: two nodes in a Binary.
* @return: Return the least common ancestor(LCA) of the two nodes.
*/
TreeNode *lowestCommonAncestor(TreeNode *root, TreeNode *A, TreeNode *B) {
// write your code here
if(!root || root == A || root == B) return root;
TreeNode *left = lowestCommonAncestor(root->left, A, B);
TreeNode *right = lowestCommonAncestor(root->right, A, B);
if(left && right) return root;
return left? left : right;
}
};
