On the line level = reversed(level) if len(res) % 2 else level you're actually appending a reverse iterator because that's what reversed() returns. You can see this if you print out `res`. You should actually call list(reversed(level)). LeetCode converts it to a list while checking your answer so it works on LeetCode. But it won't work in general. Anyway, probably a simpler way is to just reverse the level in-place. It's also more efficient. if len(res) % 2: level.reverse()
In fact when I decided to traverse every odd level in reverse order not only it was more complex it's actually not even correct eg: [1,2,3,4,null,null,5] expected : [[1] , [3,2] , [4,5]] output: [[[1] , [3,2] , [5,4]]
Hi neetcode! I'm pretty proud I did this one, although I didn't use the way that was intended to be the solution. ans = [] def dfs(node, h): if not node: return while h >= len(ans): ans.append([]) ans[h].append(node.val) dfs(node.left, h + 1) dfs(node.right, h + 1) dfs(root, 0) for i in range(len(ans)): if i % 2: ans[i].reverse()
return ans Tell me what you think. Dfs is alot easier for me to implement so I always slant towards it.
We can do it easily using 2 stack :) . Just the push and pop the elements alternatively into the stack. Time complexity : O(n) Space complexity O(n). vector zigzagLevelOrder(TreeNode* root) { if(root==NULL){return {};} vector result; vector temp; stack S1; stack S2; S1.push(root); int m,n; TreeNode* curr; while(!S1.empty() || !S2.empty()){
Great video as always. One question, are you going to link all these videos to your Neetcode All section of your website? It really helps me with keeping track of all the problems by category (Hashmaps, Binary Trees, Graphs, etc.) Thanks again for the content!
we can do it as an audience if u want. like have a public spreadsheet and do it/maintain it for him. or ill make a website with a list and ill categorize them for everyone. could be fun. if neetcode or any of u want a solution like that, just let me know. neetcode is already doing so much for free. thanks for the daily.
For each reverse, it only reverse the number of items in that level. If you look at how many total items are being reversed, it’s roughly half of them, so O(n/2) which can simplify to O(n). So really, we’re just doing O(n) extra work so O(n)+O(n)=O(2n) = O(n).
Think about it more in terms of filling the array, which is O(n), and then performing a reversal on the entire array on after filling it. This is still O(n).
Only half of the total levels (Log N) will be reversed and max level array would have N/2 items. The TC to reverse an array of N items is O(N/2). So overall TC for reversing odd level arrays is 0.5 * Log N * O(N/4), that is O(N)? I am not sure. Am I over complicating it? somebody please help.
Shouldn't the time complexity be O(n^2) since half of the height of the tree your are reversing the level. It the tree is a perfect binary tree the last level is size n/2 which effectively is n. If we are reversing the nodes of each level that is odd, then at worst we get closer to O(n^2). This is my conclusion, not sure why we shouldn't take into consideration the reversal part.
PYTHON3 ERROR: level = reversed(level) if len(result) % 2 else level -> gives a type error. FIX: To fix this, use the list type cast: level = list(reversed(level)) if len(result) % 2 else level
A totally useless optimization we can make to not have to reverse odd indexed arrays, is to use the double sided constant time addition/deletion property thing of a deque. Basically, if we are going from left -> right i.e. popping from beginning of the deque, we add the children to the end (left child first then right), else if we are going from right -> left i.e. popping from the end of the deque, we add the children to the start(right child first then left) This way we do a zig-zag bfs which kinda feels nauseating to imagine while dry running That way we visit each node only once, so atmost ~n operations, O(n) TC.
thank you for uploading the daily problems! much appreciated
Thanks for immediately uploaded solution! I decided not to reverse each second list, and used stack instead. As a result got 86% by time.
On the line
level = reversed(level) if len(res) % 2 else level
you're actually appending a reverse iterator because that's what reversed() returns. You can see this if you print out `res`. You should actually call list(reversed(level)).
LeetCode converts it to a list while checking your answer so it works on LeetCode. But it won't work in general.
Anyway, probably a simpler way is to just reverse the level in-place. It's also more efficient.
if len(res) % 2:
level.reverse()
Nice clean and fast solution!
In fact when I decided to traverse every odd level in reverse order not only it was more complex it's actually not even correct
eg: [1,2,3,4,null,null,5]
expected : [[1] , [3,2] , [4,5]]
output: [[[1] , [3,2] , [5,4]]
Hi neetcode! I'm pretty proud I did this one, although I didn't use the way that was intended to be the solution.
ans = []
def dfs(node, h):
if not node: return
while h >= len(ans): ans.append([])
ans[h].append(node.val)
dfs(node.left, h + 1)
dfs(node.right, h + 1)
dfs(root, 0)
for i in range(len(ans)):
if i % 2: ans[i].reverse()
return ans
Tell me what you think. Dfs is alot easier for me to implement so I always slant towards it.
Nice soln keep it up !
@@saifahmad141 Thank you!
We can do it easily using 2 stack :) . Just the push and pop the elements alternatively into the stack. Time complexity : O(n) Space complexity O(n).
vector zigzagLevelOrder(TreeNode* root) {
if(root==NULL){return {};}
vector result;
vector temp;
stack S1;
stack S2;
S1.push(root);
int m,n;
TreeNode* curr;
while(!S1.empty() || !S2.empty()){
while(!S1.empty()){
curr=S1.top();
S1.pop();
temp.push_back(curr->val);
if(curr->left){S2.push(curr->left);}
if(curr->right){S2.push(curr->right);}
}
if(temp.size()){result.push_back(temp);
temp.clear();}
while(!S2.empty()){
curr=S2.top();
S2.pop();
temp.push_back(curr->val);
if(curr->right){S1.push(curr->right);}
if(curr->left){S1.push(curr->left);}
}
if(temp.size()){
result.push_back(temp);
temp.clear();}
}
return result;
}
Great video as always. One question, are you going to link all these videos to your Neetcode All section of your website? It really helps me with keeping track of all the problems by category (Hashmaps, Binary Trees, Graphs, etc.) Thanks again for the content!
we can do it as an audience if u want. like have a public spreadsheet and do it/maintain it for him. or ill make a website with a list and ill categorize them for everyone. could be fun. if neetcode or any of u want a solution like that, just let me know.
neetcode is already doing so much for free. thanks for the daily.
@@uptwist2260 cool idea to make a website mate! Let me know if you're making the website, I'll contribute!!
Thank you for another great explanation sir !
Reverse in itself is O(N), how is the time complexity still O(N)?
Yes even I had the same doubt?..did u got this cleared?...
For each reverse, it only reverse the number of items in that level. If you look at how many total items are being reversed, it’s roughly half of them, so O(n/2) which can simplify to O(n). So really, we’re just doing O(n) extra work so O(n)+O(n)=O(2n) = O(n).
Think about it more in terms of filling the array, which is O(n), and then performing a reversal on the entire array on after filling it. This is still O(n).
@@chirpy7961look at my solution
Only half of the total levels (Log N) will be reversed and max level array would have N/2 items. The TC to reverse an array of N items is O(N/2). So overall TC for reversing odd level arrays is 0.5 * Log N * O(N/4), that is O(N)? I am not sure. Am I over complicating it? somebody please help.
Thank you so much
Just Awesome!!!
Leetcode102 Would be also cool to see in your explanation :)
Nice explanation . Could you please post the videos for the leetcode problem no 979 and 2266 ? They are interesting as well as tricky.
Thank you
Thanks!
I tried using the logic of BFS traversal and for every alternate level I popped either from the right or the left but I got time limit exceeded error.
my bad I used a list in the wrong for loop XD
why not just swap the order of adding node.right and node.left depending on which level we are on for reduced space complexity
For that len(q) thing, U could have made this solution recursive to make in language independent innit?
Shouldn't the time complexity be O(n^2) since half of the height of the tree your are reversing the level. It the tree is a perfect binary tree the last level is size n/2 which effectively is n. If we are reversing the nodes of each level that is odd, then at worst we get closer to O(n^2). This is my conclusion, not sure why we shouldn't take into consideration the reversal part.
PYTHON3 ERROR:
level = reversed(level) if len(result) % 2 else level -> gives a type error.
FIX: To fix this, use the list type cast:
level = list(reversed(level)) if len(result) % 2 else level
A totally useless optimization we can make to not have to reverse odd indexed arrays, is to use the double sided constant time addition/deletion property thing of a deque.
Basically,
if we are going from left -> right i.e. popping from beginning of the deque, we add the children to the end (left child first then right),
else if we are going from right -> left i.e. popping from the end of the deque, we add the children to the start(right child first then left)
This way we do a zig-zag bfs which kinda feels nauseating to imagine while dry running
That way we visit each node only once, so atmost ~n operations, O(n) TC.