ntree.aiLowest Common Ancestor
Lowest Common Ancestor
mediumsolvedattempted
Given two nodes p and q from a tree, return their lowest common ancestor.
Each node has a reference to its parent node.
A node counts as a descendant of itself, so if one of p and q is an ancestor of the other, that ancestor is the answer.
Example 1:
3
5
6
2
7
4
1
0
8
Input: tree = [3, null, 5, 1, null, 6, 2, null, 0, 8, null, null, 7, 4], p = 4, q = 6
Output: 5
Example 2:
3
5
6
2
7
4
1
0
8
Input: tree = [3, null, 5, 1, null, 6, 2, null, 0, 8, null, null, 7, 4], p = 5, q = 4
Output: 5
Explanation: 5 is an ancestor of 4, and a node counts as a descendant of itself.
Constraints:
2 <= the number of nodes in the tree <= 10^5-10^9 <= Node.val <= 10^9
# Definitions:# class Node:# def __init__(self, val=0, children=None, parent=None):# self.val = val# self.children = children if children is not None else []# self.parent = parent def lowestCommonAncestor(p: Node, q: Node) -> Node: pass 3
5
6
2
7
4
1
0
8
Press Visualise to step through your code.