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.
1function TreeNode(val) {
2 this.val = val;
3 this.left = this.right = null;
4}
The JavaScript code implements a straightforward recursion strategy similar to other languages. It recursively checks the presence of p or q and uses the results from left and right recursive calls to determine the potential LCA.
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.
public class TreeNode {
public int val;
public TreeNode left;
public TreeNode right;
public TreeNode(int x) { val = x; }
}
public class Solution {
private bool GetPath(TreeNode root, TreeNode target, List<TreeNode> path) {
if (root == null) return false;
path.Add(root);
if (root == target) return true;
if ((root.left != null && GetPath(root.left, target, path)) ||
(root.right != null && GetPath(root.right, target, path)))
return true;
path.RemoveAt(path.Count - 1);
return false;
}
public TreeNode LowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
List<TreeNode> pathP = new List<TreeNode>(), pathQ = new List<TreeNode>();
GetPath(root, p, pathP);
GetPath(root, q, pathQ);
int i;
for (i = 0; i < pathP.Count && i < pathQ.Count; i++) {
if (pathP[i] != pathQ[i]) break;
}
return pathP[i - 1];
}
}C# uses lists to discern the root-to-node paths for both p and q, subsequently revealing the shared ancestor at the last intersection point.