Sponsored
Sponsored
This approach uses recursion to traverse the tree starting from the root. If the current node is either p or q, then the node is returned upwards in the recursion stack as the potential LCA. Otherwise, we continue to search both left and right subtrees. If both subtrees return non-null values, it means p and q are in different subtrees, and the current node is the LCA. If only one subtree returns a non-null value, it means both nodes are located in that subtree and that subtree's root should be the LCA.
Time Complexity: O(N), where N is the number of nodes in the binary tree, as we visit each node only once.
Space Complexity: O(N) due to the recursion stack when the tree is completely unbalanced.
1public class TreeNode {
2 public int val;
3 public TreeNode left;
4 public TreeNode right;
5 public TreeNode(int x) { val = x; }
6}
7
8public class Solution {
9 public TreeNode LowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
10 if (root == null || root == p || root == q) return root;
11 TreeNode left = LowestCommonAncestor(root.left, p, q);
12 TreeNode right = LowestCommonAncestor(root.right, p, q);
13 if (left != null && right != null) return root;
return left != null ? left : right;
}
}This approach leverages direct recursion in C# as well, mirroring the detailed functioning aforementioned in other implementations, ensuring consistent behavior across different programming paradigms.
The basic idea is to find the paths from the root to the two nodes p and q. Once you have the paths, compare them to find the deepest common node. This method is straightforward, using known operations to reconfirm ancestor status along determined paths.
Time Complexity: O(N) due to double traversal in finding paths for each node.
Space Complexity: O(H), where H is the height of the tree for storing path information.
In JavaScript, this implementation builds full root-to-target paths in arrays, using them to identify the last shared element as the lowest common ancestor.