/**
* 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 {
private:
TreeNode* lowestCommonAncestorOriginal(TreeNode* root, TreeNode* p, TreeNode* q) {
if (!root || root == p || root == q) return root;
auto left = lowestCommonAncestorOriginal(root->left, p, q);
auto right = lowestCommonAncestorOriginal(root->right, p, q);
if (left && right) return root;
return left ? left : right;
}
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if (!root || !p || !q) return nullptr;
auto res = lowestCommonAncestorOriginal(root, p, q);
if (res == p) {
return lowestCommonAncestorOriginal(p, q, q) ? res : nullptr;
} else if (res == q) {
return lowestCommonAncestorOriginal(q, p, p) ? res : nullptr;
}
return res;
}
};