Lowest Common Ancestor of a Binary Tree III

Link

Description

Given two nodes of a binary tree p and q, return their lowest common ancestor (LCA).

Each node will have a reference to its parent node. The definition for Node is below:

class Node {
    public int val;
    public Node left;
    public Node right;
    public Node parent;
};

According to the definition of LCA on Wikipedia: "The lowest common ancestor of two nodes p and q in a tree T is the lowest node that has both p and q as descendants (where we allow a node to be a descendant of itself)."

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

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 exist in the tree.

Solution

Way 1

/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* left;
    Node* right;
    Node* parent;
};
*/

class Solution {
public:
    Node* lowestCommonAncestor(Node* p, Node * q) {
        unordered_set<Node*> seen;
        while (p) {
            seen.insert(p);
            p = p->parent;
        }

        while (q) {
            if (seen.find(q) != seen.end()) return q;
            q = q->parent;
        }

        return nullptr;
    }
};

Way 2

/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* left;
    Node* right;
    Node* parent;
};
*/

class Solution {
private:
    int getDepth(Node* p) {
        int depth = 0;
        auto curr = p;
        while (curr) {
            curr = curr->parent;
            depth++;
        }
        return depth;
    }

public:
    Node* lowestCommonAncestor(Node* p, Node * q) {
        int pDepth = getDepth(p), qDepth = getDepth(q);

        while (pDepth > qDepth) {
            pDepth--;
            p = p->parent;
        }
        while (qDepth > pDepth) {
            qDepth--;
            q = q->parent;
        }

        while (p != q) {
            p = p->parent;
            q = q->parent;
        }

        return p;
    }
};

• Time complexity: \(O(h)\), where \(h\) is the depth of the tree;
• Space complexity: \(O(1)\), as we do not use any additional memory for traversal.

Way 3

Similar to Leetcode 160: Intersection of Two Linked Lists.

/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* left;
    Node* right;
    Node* parent;
};
*/

class Solution {
public:
    Node* lowestCommonAncestor(Node* p, Node * q) {
        auto a = p, b = q;
        while (a != b) {
            a = a ? a->parent : q;
            b = b ? b->parent : p;
        }
        return a;
    }
};