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:
[2, 105].-109 <= Node.val <= 109Node.val are unique.p != qp and q exist in the tree.We use a hash table vis to record all nodes on the path from node p to the root node. Then we start from node q and traverse towards the root node. If we encounter a node that exists in the hash table vis, then this node is the nearest common ancestor of p and q, and we can return it directly.
The time complexity is O(n), and the space complexity is O(n). Here, n is the number of nodes in the binary tree.
Java
C++
Go
TypeScript
We can use two pointers a and b to point to nodes p and q respectively, and then traverse towards the root node. When a and b meet, it is the nearest common ancestor of p and q. Otherwise, if pointer a traverses to the root node, then we let it point to node q, and do the same for pointer b. In this way, when the two pointers meet, it is the nearest common ancestor of p and q.
The time complexity is O(n), where n is the number of nodes in the binary tree. The space complexity is O(1).
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Hash Table | — |
| Two Pointers | — |
L27. Lowest Common Ancestor in Binary Tree | LCA | C++ | Java • take U forward • 379,733 views views
Watch 9 more video solutions →Practice Lowest Common Ancestor of a Binary Tree III with our built-in code editor and test cases.
Practice on FleetCode