Tree DFS
LC #236Medium
Lowest Common Ancestor of Binary Tree
Tree DFS
MetaAmazonGoogleMicrosoftLinkedInProblem
Find the LCA of two nodes p and q in a general binary tree (not necessarily a BST).
treedfs
Constraints
- ›2 ≤ number of nodes ≤ 10⁵
- ›-10⁹ ≤ node.val ≤ 10⁹
- ›p and q exist in the tree
- ›p ≠ q
Example
Input
root = [3,5,1,6,2,0,8], p = 5, q = 1Output
3Why
Node 3 is the deepest ancestor of both 5 and 1