Lowest Common Ancestor

题目：

Given the root and two nodes in a Binary Tree. Find the lowest common ancestor(LCA) of the two nodes.

The lowest common ancestor is the node with largest depth which is the ancestor of both nodes.

分析：

这题目是一个典型的divide and conquer，第二遍做的时候只记得有左右，左中，右中三种情况，但是忘记了具体该怎么写。divide and conquer和dfs并不完全一样，首先他有返回值，其次一般都是先做left和right，然后在拿到返回值之后，开始判断用的if逻辑。

解法：

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 == NULL) {
            return root;
        }

        if (root->val == A->val || root->val == B->val) {
            return root;
        }

        TreeNode* left = lowestCommonAncestor(root->left, A, B);
        TreeNode* right = lowestCommonAncestor(root->right, A, B);

        if (left != NULL && right != NULL) {
            return root;
        }

        if (left != NULL) {
            return left;
        }

        if (right != NULL) {
            return right;
        }
        return NULL;
    }
};