Leetcode 2415: Reverse Odd Levels of Binary Tree
Given the root of a perfect binary tree, reverse the values of the nodes at each odd level of the tree. The level of a node is defined as the number of edges along the path from the root to the node. A perfect binary tree is one where all nodes have two children and all leaves are on the same level.
Problem
Approach
Steps
Complexity
Input: The input consists of a perfect binary tree represented by its root node.
Example: root = [4, 2, 6, 1, 3, 5, 7]
Constraints:
• 1 <= Node.val <= 10^5
• The number of nodes in the tree is between 1 and 214.
Output: Return the root of the modified binary tree after reversing the nodes at each odd level.
Example: Output: [4, 6, 2, 1, 3, 5, 7]
Constraints:
Goal: The goal is to reverse the node values at each odd level while maintaining the structure of the tree.
Steps:
• 1. Perform a level order traversal (breadth-first search) of the binary tree.
• 2. For each level, check if it is odd or even.
• 3. If the level is odd, collect the node values at that level and reverse the order of these values.
• 4. Update the node values at the odd levels with the reversed values.
Goal: The solution must handle perfect binary trees efficiently.
Steps:
• The number of nodes in the tree is in the range [1, 214].
• Each node has a value between 0 and 10^5.
Assumptions:
• The input tree is always a perfect binary tree.
• Input: Input: root = [4, 2, 6, 1, 3, 5, 7]
• Explanation: At level 1, the nodes are 2 and 6, which are reversed to become 6 and 2. The final output is [4, 6, 2, 1, 3, 5, 7].
Approach: The approach involves performing a level order traversal of the tree. At each odd level, we reverse the node values and update the tree accordingly.
Observations:
• We can perform a level-order traversal using a queue.
• At each odd level, we reverse the node values and update the tree structure.
• Since the binary tree is perfect, we can be sure that all levels are fully populated.
Steps:
• 1. Initialize a queue and start with the root node.
• 2. Use a while loop to process nodes level by level.
• 3. For each level, check if it is odd. If it is, reverse the node values at that level.
• 4. Continue processing all levels of the tree until the traversal is complete.
Empty Inputs:
• The input tree will always have at least one node, as per the problem constraints.
Large Inputs:
• The tree can have up to 214 nodes, which should be handled efficiently in terms of time and space.
Special Values:
• If the tree has only one level, no changes will be made as there are no odd levels.
Constraints:
• Ensure the algorithm works efficiently for a tree with up to 214 nodes.
TreeNode* reverseOddLevels(TreeNode* root) {
if(!root) return root;
queue<TreeNode*> q;
q.push(root);
vector<int> vals;
int level = 0;
while(!q.empty()) {
int sz = q.size();
vector<int> temp;
for(int i = 0; i < sz; i++) {
TreeNode* node = q.front(); q.pop();
if(level %2) node->val= vals[sz- i - 1];
if(node->left) {
q.push(node->left);
temp.push_back(node->left->val);
}
if(node->right) {
q.push(node->right);
temp.push_back(node->right->val);
}
}
vals = temp;
level++;
}
return root;
}
1 : Function Declaration
TreeNode* reverseOddLevels(TreeNode* root) {
Function declaration for 'reverseOddLevels'. It takes the root of a binary tree as input.
2 : Base Case
if(!root) return root;
Checks if the root is null, and if so, returns null immediately (base case for recursion).
3 : Queue Initialization
queue<TreeNode*> q;
Initialize a queue to facilitate level-order traversal (BFS).
4 : Push Root to Queue
q.push(root);
Push the root of the tree into the queue to begin the traversal.
5 : Initialize vals
vector<int> vals;
Create a vector to store the node values at each level of the tree.
6 : Level Initialization
int level = 0;
Initialize a variable 'level' to track the current level during traversal.
7 : While Loop Start
while(!q.empty()) {
Begin the loop to process nodes in the queue until it is empty.
8 : Queue Size
int sz = q.size();
Determine the number of nodes at the current level by checking the size of the queue.
9 : Temporary Storage
vector<int> temp;
Create a temporary vector to store the values of the nodes at the current level.
10 : For Loop Start
for(int i = 0; i < sz; i++) {
Start a loop to process each node at the current level.
11 : Dequeue Node
TreeNode* node = q.front(); q.pop();
Dequeue the front node and store it in 'node' for processing.
12 : Odd Level Check
if(level %2) node->val= vals[sz- i - 1];
If the current level is odd, reverse the values of the nodes at that level.
13 : Left Child Check
if(node->left) {
Check if the current node has a left child.
14 : Push Left Child
q.push(node->left);
Push the left child of the node into the queue for future processing.
15 : Store Left Child Value
temp.push_back(node->left->val);
Store the value of the left child in the temporary vector.
16 : Right Child Check
if(node->right) {
Check if the current node has a right child.
17 : Push Right Child
q.push(node->right);
Push the right child of the node into the queue.
18 : Store Right Child Value
temp.push_back(node->right->val);
Store the value of the right child in the temporary vector.
19 : Update vals
vals = temp;
Update the 'vals' vector to hold the values of the current level for the next iteration.
20 : Level Increment
level++;
Increment the level counter to track the next level.
21 : Return Root
return root;
Return the modified tree with odd levels reversed.
Best Case: O(n)
Average Case: O(n)
Worst Case: O(n)
Description: The time complexity is linear, as we visit each node once.
Best Case: O(n)
Worst Case: O(n)
Description: The space complexity is O(n) for the queue used in the level-order traversal.
| LeetCode Solutions Library / DSA Sheets / Course Catalog |
|---|
comments powered by Disqus