/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
TreeNode *lowestCommonAncestor(TreeNode *root, TreeNode *p, TreeNode *q) {
if (root == nullptr) {
return nullptr;
}
if (root == p || root == q) {
return root;
}
TreeNode *leftSubtree = lowestCommonAncestor(root->left, p, q);
TreeNode *rightSubtree = lowestCommonAncestor(root->right, p, q);
if (leftSubtree == nullptr) {
// Both p and q are not located in the left subtree.
// Because p and q exist in the binary tree, they are in the
// right subtree.
return rightSubtree;
}
if (rightSubtree == nullptr) {
// Both p and q are not located in the right subtree.
// Because p and q exist in the binary tree, they are in the
// left subtree.
return leftSubtree;
}
// Both leftSubtree and rightSubtree are not nullptr.
// root is the lowest common ancestor of p and q.
return root;
}
};
My Solution Solution 1: DFS (recursion) The Key Idea for Solving This Coding Question C++ Code /** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right;
Jun 6, 2025MyCircularQueueO(k)
Apr 20, 2025O(m)
Mar 4, 2025O(n)n is the length of nums.
Feb 19, 2025or
By clicking below, you agree to our terms of service.
New to HackMD? Sign up