• 87.9k
• 14
• 104
• 325

• 26.1k
• 13
• 47
• 114

• 97.7k
• 5
• 126
• 341

Trying my hand at Leet 236.

This is the final version.
My first version can be found here.

/**
 * 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:
 // So if we can find `q` in the subtree routed by c
 bool match(TreeNode* c, TreeNode* q)
 {
 // recursive out
 if (c == nullptr) {
 return false;
 }
 // We found it.
 if (c == q) {
 return true;
 }
 // Search left and right.
 // Note: The '||' is shortcut operator. So if we find in the left
 // we don't search the right.
 return match(c->left, q) || match(c->right, q);
 }
 TreeNode* lca(bool& found, TreeNode* c, TreeNode*& p, TreeNode*& q)
 {
 // recursive out.
 if (c == nullptr) {
 return nullptr;
 }
 // See if the current node is p or q.
 if (c == p) {
 found = true;
 }
 else if (c == q) {
 // If it is q then swap p and q.
 // This makes it easy to know what to pass to match()
 // We will always pass q.
 std::swap(p, q);
 found = true;
 }
 // Note: If we have found one then found is true and the other is in q.
 TreeNode* find = found
 // We have found one. See if the other is the left subtree.
 // If so then c is the lca.
 ? (match(c->left, q) ? c : nullptr)
 // We have not found either. So recursively try again.
 : lca(found, c->left, p, q);
 // Only need to search the right tree if nothing was found in the left.
 if (find == nullptr) {
 find = found
 // We have found one. See if the other is the right subtree.
 // If so then c is the lca.
 ? (match(c->right, q) ? c : nullptr)
 // We have not found either. So recursively try again.
 : lca(found, c->right, p, q);
 }
 // Note this may be nullptr
 return find;
 }
 TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q)
 {
 // Optimization.
 // If either node is root then this is the common ancestor
 // as we know the other node must exist and thus be in one of
 // the branches.
 if (root == p || root == q) {
 return root;
 }
 bool found = false;
 // Search left branch.
 TreeNode* find = lca(found, root->left, p, q);
 // If LCA was not found the search the right.
 if (!find) {
 // Optimization.
 // If we found either of p or q in the left, but not
 // the other one. Then we know the other one must be
 // in the right branch. Thus we don't need to search
 // the right branch.
 find = found ? root : lca(found, root->right, p, q);
 }
 return find;
 }
};