LeetCode 314: Binary Tree Vertical Order Traversal
LeetCode 314 Solution Explanation
Explanation:
To perform a vertical order traversal of a binary tree, we can use a TreeMap (or HashMap with a sorting mechanism) to store nodes based on their horizontal distance from the root. We can do a level order traversal of the tree while keeping track of the horizontal distance of each node.
- Start with the root node and horizontal distance as 0.
- Use a queue to perform level order traversal while updating the horizontal distance of each node.
- Maintain a TreeMap to store nodes based on their horizontal distance.
- After traversing the tree, extract the nodes from the TreeMap in sorted order of horizontal distance to get the vertical order traversal.
Time Complexity: O(n log n) where n is the number of nodes in the binary tree. Space Complexity: O(n) for the TreeMap and the queue.
:
LeetCode 314 Solutions in Java, C++, Python
import java.util.*;
class TreeNode {
int val;
TreeNode left, right;
TreeNode(int val) {
this.val = val;
}
}
public List<List<Integer>> verticalOrder(TreeNode root) {
List<List<Integer>> result = new ArrayList<>();
if (root == null) return result;
TreeMap<Integer, List<Integer>> map = new TreeMap<>();
Queue<TreeNode> queue = new LinkedList<>();
Queue<Integer> hd = new LinkedList<>();
queue.offer(root);
hd.offer(0);
while (!queue.isEmpty()) {
TreeNode node = queue.poll();
int col = hd.poll();
if (!map.containsKey(col)) {
map.put(col, new ArrayList<>());
}
map.get(col).add(node.val);
if (node.left != null) {
queue.offer(node.left);
hd.offer(col - 1);
}
if (node.right != null) {
queue.offer(node.right);
hd.offer(col + 1);
}
}
for (List<Integer> list : map.values()) {
result.add(list);
}
return result;
}Interactive Code Editor for LeetCode 314
Improve Your LeetCode 314 Solution
Use the editor below to refine the provided solution for LeetCode 314. 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...