LeetCode Link: 236. Lowest Common Ancestor of a Binary Tree
Language: C#
Problem Statement
Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.
According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”
Examples
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, 105].
- -109 <= Node.val <= 109
- All Node.val are unique.
- p != q
- p and q will exist in the tree.
Solution
/**
* Definition for a binary tree node.
* public class TreeNode {
* public int val;
* public TreeNode left;
* public TreeNode right;
* public TreeNode(int x) { val = x; }
* }
*/
public class Solution
{
public TreeNode LowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q)
{
if (root is null)
{
return null;
}
var l = LowestCommonAncestor(root.left, p, q);
var r = LowestCommonAncestor(root.right, p, q);
if (root == p || root == q)
{
return root;
}
if (l != null && r != null)
{
return root;
}
return l ?? r;
}
}
Complexity
Time Complexity: O(N)
Space Complexity: O(N)