给定一棵二叉树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义： “对于有根树T的两个结点u、v，最近公共祖先表示一个结点x，满足x是u、v的祖先且x的深度尽可能大。”（一个节点也可以是它自己的祖先）

        _______3______

       /              \

    ___5__          ___1__

   /      \        /      \

   6      _2       0       8

         /  \

         7   4

例如，节点5和节点1的最近公共祖先是节点3；节点5和节点4的最近公共祖先是节点5，因为根据定义，一个节点可以是它自己的祖先。

 /**

  * Definition for a binary tree node.

  * struct TreeNode {

  *     int val;

  *     TreeNode *left;

  *     TreeNode *right;

  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}

  * };

  */

 class Solution {

 public:

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

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

             return root;

         TreeNode* left = lowestCommonAncestor(root->left, p, q);

         TreeNode* right = lowestCommonAncestor(root->right, p, q);

         if(left && right)

             return root;

         return left == NULL ? right : left;

     }

 };