LeetCode 1650. Lowest Common Ancestor of a Binary Tree III

Question

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).”

https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree-iii/

Solution

• Solution1

class Solution {
    /*
    public Node lowestCommonAncestor(Node p, Node q) {
        Set<Node> set = new HashSet<>();
        while(true){
            if (p != null && !set.add(p)) return p;
            if (q != null && !set.add(q)) return q;
            if (p != null) p = p.parent;
            if (q != null) q = q.parent;
        }
        
    }
    Time complexity: O(n)

	Space complexity: O(n)
    */
    public Node lowestCommonAncestor(Node p, Node q){
        Node a = p, b = q;
        while (a != b){
            a = a == null ? q : a.parent;
            b = b == null ? p : b.parent;
        }
        return a;
    }
}

Complexity:

Time complexity: O(n)

Space complexity: O(1)