236. Lowest Common Ancestor of a Binary Tree

1. Description

Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.
According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”

2. Example

Example 1:

Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
Output: 3
Explanation: The LCA of nodes 5 and 1 is 3.

Example 2:

Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
Output: 5
Explanation: The LCA of nodes 5 and 4 is 5, since a node can be a descendant of itself according to the LCA definition.

Example 3:
Input: root = [1,2], p = 1, q = 2
Output: 1

3. Constraints

• The number of nodes in the tree is in the range [2, $10^5$].
• $-10^9$ <= Node.val <= $10^9$
• All Node.val are unique.
• p != q
• p and q will exist in the tree.

4. Solutions

Depth-First Search

n is number of nodes in the root
Time complexity: O(n)
Space complexity: O(n)

class Solution {
public:
    TreeNode *lowestCommonAncestor(TreeNode *root, TreeNode *p, TreeNode *q) {
        vector<TreeNode *> path;
        traverse_(root, path, p, q);

        TreeNode *result = nullptr;
        for (int i = 0; i < p_path_.size() && i < q_path_.size() && p_path_[i] == q_path_[i]; ++i) {
            result = p_path_[i];
        }

        return result;
    }

private:
    vector<TreeNode *> p_path_;
    vector<TreeNode *> q_path_;

    void traverse_(TreeNode *root, vector<TreeNode *> &path, TreeNode *p, TreeNode *q) {
        if (root != nullptr) {
            path.push_back(root);
            if (root == p) {
                p_path_ = path;
            } else if (root == q) {
                q_path_ = path;
            }

            traverse_(root->left, path, p, q);
            traverse_(root->right, path, p, q);
            path.pop_back();
        }
    }
};