Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/1650.html
1650. Lowest Common Ancestor of a Binary Tree III
Level
Medium
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
andq
exist in the tree.
Solution  Set
Use a set to store nodes. Start from p
and obtain all the nodes from p
to the root node using the nodes’ parents. Then start from q
and move towards the root. If a node is already in the set, then the node is a common ancestor of p
and q
. The first common ancestor that is in the set is the lowest common ancestor of p
and q
.
Solution  2 pointers
The idea is as follows: we will use 2 pointers
(pointerA, pointerB) that go from nodeA and nodeB upwards
respectively. Assume nodeA locates at a shallower level than nodeB, i.e. depth(nodeA) < depth(nodeB), pointerA will reach the top quicker than pointerB.
Suppose the difference in depth between nodeA and nodeB is diff
.
By the time pointerA reaches the top, pointerB will be diff
levels behind. Now if pointerA resets its path and continues upwards from nodeB instead of nodeA, it will need diff
steps to reach the level of nodeA, by which time pointerB has already caught up and will be at the same level of pointerA
(pointerB restarts from nodeA after reaching the top).
Now the only thing to do is to compare pointerA and pointerB on the way up. If pointerA and pointerB points to the same node
, we’ve found the lowest common ancestor
.

/* // Definition for a Node. class Node { public int val; public Node left; public Node right; public Node parent; }; */ class Solution { public Node lowestCommonAncestor(Node p, Node q) { Set<Node> set = new HashSet<Node>(); Node temp = p; while (temp != null) { set.add(temp); temp = temp.parent; } temp = q; while (temp != null) { if (set.contains(temp)) break; else temp = temp.parent; } return temp; } } ############ /* // Definition for a Node. class Node { public int val; public Node left; public Node right; public Node parent; }; */ class Solution { public Node lowestCommonAncestor(Node p, Node q) { Node a = p, b = q; while (a != b) { a = a.parent == null ? q : a.parent; b = b.parent == null ? p : b.parent; } return a; } }

// OJ: https://leetcode.com/problems/lowestcommonancestorofabinarytreeiii/ // Time: O(N) // Space: O(1) class Solution { int getLength(Node *p) { int ans = 0; for (; p>parent; p = p>parent, ++ans); return ans; } public: Node* lowestCommonAncestor(Node* p, Node * q) { int a = getLength(p), b = getLength(q); if (a < b) swap(a, b), swap(p, q); a = b; while (a > 0) p = p>parent; while (p != q) p = p>parent, q = q>parent; return p; } };

""" # Definition for a Node. class Node: def __init__(self, val): self.val = val self.left = None self.right = None self.parent = None """ class Solution: def lowestCommonAncestor(self, p: 'Node', q: 'Node') > 'Node': a, b = p, q while a != b: a = a.parent if a.parent else q b = b.parent if b.parent else p return a ############ # ref: https://iamageek.medium.com/leetcode1650lowestcommonancestorofabinarytreeiii6d008b93376c def lowestCommonAncestor(self, a: 'Node', b: 'Node') > 'Node': ancestors = set() while a is not None: ancestors.add(a) a = a.parent while b is not None: if b in ancestors: return b b = b.parent # or another one def lowestCommonAncestor(self, a: 'Node', b: 'Node') > 'Node': pointerA, pointerB = a, b while pointerA != pointerB: pointerA = pointerA.parent if pointerA else b pointerB = pointerB.parent if pointerA else a return pointerA

/** * Definition for Node. * type Node struct { * Val int * Left *Node * Right *Node * Parent *Node * } */ func lowestCommonAncestor(p *Node, q *Node) *Node { a, b := p, q for a != b { if a.Parent != nil { a = a.Parent } else { a = q } if b.Parent != nil { b = b.Parent } else { b = p } } return a }

/** * Definition for a binary tree node. * class Node { * val: number * left: Node  null * right: Node  null * parent: Node  null * constructor(val?: number, left?: Node  null, right?: Node  null, parent?: Node  null) { * this.val = (val===undefined ? 0 : val) * this.left = (left===undefined ? null : left) * this.right = (right===undefined ? null : right) * this.parent = (parent===undefined ? null : parent) * } * } */ function lowestCommonAncestor(p: Node  null, q: Node  null): Node  null { const vis: Set<Node> = new Set(); for (let node = p; node; node = node.parent) { vis.add(node); } for (let node = q; ; node = node.parent) { if (vis.has(node)) { return node; } } }