二叉树的最近公共祖先

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

思路：

假设二叉树为root,指定的两个节点分别为p,q。三种情况，如果p，q分别位于root的两侧，则root就是答案，如果位于一侧，则递归。具体递归代码，递归出口条件为root为nullptr,或者root==p或者root==q时，返回root。然后分别求左右子树中，p和q的公共祖先。结果分别为left和right，如果left、right都有值，则答案为root。如果只有一个有值，则答案为有值的那个

代码：

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if(!root || root == p || root == q) return root;
        TreeNode* l = lowestCommonAncestor(root->left,p,q);
        TreeNode* r = lowestCommonAncestor(root->right,p,q);
        return l?(r?root:l):r;
    }
};