LeetCode 1123: Lowest Common Ancestor of Deepest Leaves Solution
Master LeetCode problem 1123 (Lowest Common Ancestor of Deepest Leaves), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.
1123. Lowest Common Ancestor of Deepest Leaves
Problem Explanation
Explanation:
To find the lowest common ancestor of the deepest leaves in a binary tree, we can perform a postorder traversal to get the depth of each node and find the deepest leaves. Then, we can recursively find the lowest common ancestor of the deepest leaves.
- Perform a postorder traversal to calculate the depth of each node.
- Find the deepest leaves by traversing the tree again.
- Recursively find the lowest common ancestor of the deepest leaves.
Time complexity: O(n) where n is the number of nodes in the tree. Space complexity: O(n) for the recursive stack and additional space used for storing depths and leaves. :
Solution Code
class Solution {
public TreeNode lcaDeepestLeaves(TreeNode root) {
return dfs(root).node;
}
private Result dfs(TreeNode node) {
if (node == null) {
return new Result(null, 0);
}
Result left = dfs(node.left);
Result right = dfs(node.right);
if (left.depth > right.depth) {
return new Result(left.node, left.depth + 1);
} else if (left.depth < right.depth) {
return new Result(right.node, right.depth + 1);
} else {
return new Result(node, left.depth + 1);
}
}
class Result {
TreeNode node;
int depth;
Result(TreeNode node, int depth) {
this.node = node;
this.depth = depth;
}
}
}Try It Yourself
Loading code editor...
Related LeetCode Problems
Frequently Asked Questions
How to solve LeetCode 1123 (Lowest Common Ancestor of Deepest Leaves)?
This page provides optimized solutions for LeetCode problem 1123 (Lowest Common Ancestor of Deepest Leaves) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.
What is the time complexity of LeetCode 1123 (Lowest Common Ancestor of Deepest Leaves)?
The time complexity for LeetCode 1123 (Lowest Common Ancestor of Deepest Leaves) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.
Can I run code for LeetCode 1123 on DevExCode?
Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 1123 in Java, C++, or Python.