LeetCode 1740: Find Distance in a Binary Tree
LeetCode 1740 Solution Explanation
Explanation
To find the distance between two nodes in a binary tree, we first need to find the lowest common ancestor (LCA) of the two nodes. Once we have the LCA, we can calculate the distance as the sum of the distances from the LCA to each of the target nodes.
We can find the LCA using a recursive approach. Starting from the root, we traverse the tree in a depth-first manner. If we find either of the target nodes, we return that node. If we find both nodes on different sides of the current node, then the current node is the LCA. We recursively search in the left and right subtrees until we find both nodes on different sides or one of the nodes.
The distance between a node and its descendant can be calculated as the sum of the distances from the node to the descendant nodes.
Time complexity: O(n) where n is the number of nodes in the binary tree. Space complexity: O(n) for the recursive call stack.
LeetCode 1740 Solutions in Java, C++, Python
class TreeNode {
int val;
TreeNode left, right;
TreeNode(int x) {
val = x;
}
}
class Solution {
public int findDistance(TreeNode root, int p, int q) {
TreeNode lca = findLCA(root, p, q);
int distP = findDistanceToNode(lca, p, 0);
int distQ = findDistanceToNode(lca, q, 0);
return distP + distQ;
}
private TreeNode findLCA(TreeNode root, int p, int q) {
if (root == null || root.val == p || root.val == q) {
return root;
}
TreeNode left = findLCA(root.left, p, q);
TreeNode right = findLCA(root.right, p, q);
if (left != null && right != null) {
return root;
}
return left != null ? left : right;
}
private int findDistanceToNode(TreeNode root, int target, int distance) {
if (root == null) {
return -1;
}
if (root.val == target) {
return distance;
}
int left = findDistanceToNode(root.left, target, distance + 1);
int right = findDistanceToNode(root.right, target, distance + 1);
return Math.max(left, right);
}
}Interactive Code Editor for LeetCode 1740
Improve Your LeetCode 1740 Solution
Use the editor below to refine the provided solution for LeetCode 1740. Select a programming language and try the following:
- Add import statements if required.
- Optimize the code for better time or space complexity.
- Add test cases to validate edge cases and common scenarios.
- Handle error conditions or invalid inputs gracefully.
- Experiment with alternative approaches to deepen your understanding.
Click "Run Code" to execute your solution and view the output. If errors occur, check the line numbers and debug accordingly. Resize the editor by dragging its bottom edge.
Loading editor...