面试题 68：树中两个节点的最低公共祖先.md

试题链接：88. 树中两个结点的最低公共祖先 - AcWing题库

方法一：递归

• 思路：递归返回的结果就是最低公共祖先所在节点，使用中序遍历的思路，先递归处理左右子树，如果有一边返回为空，则取非空的一边，如果两边都有，则当前节点就是最低公共祖先。
• 时间复杂度：O(n)
• 空间复杂度：O(n)

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