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.
1#include <iostream>
2using namespace std;
3
4struct TreeNode {
5 int val;
6 TreeNode *left;
7 TreeNode *right;
8 TreeNode(int x) : val(x), left(NULL), right(NULL) {}
9};
10
11class Solution {
12public:
13 TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
14 if (!root || root == p || root == q) return root;
TreeNode* left = lowestCommonAncestor(root->left, p, q);
TreeNode* right = lowestCommonAncestor(root->right, p, q);
if (left && right) return root;
return left ? left : right;
}
};This C++ code employs a DFS strategy to find the LCA in a binary tree. The function is similar to the C implementation, traversing the tree and returning the current node if it matches one of the nodes we are finding. If both left and right are non-null, the current node is the 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.
In C, we maintain arrays to keep track of paths from the root to the target nodes and compare these paths to find their last common node.