# Tag Info

5

Your solution isn't $O(n)$ but $O(2^n)$. Your assumption that the tree is complete and thus your analysis is incorrect. Already LeetCode's second example tree isn't complete. And consider this tree: That tree only has 25 nodes, but your solution creates thousands of Nones for subtrees that aren't there. (That is, your actual code presumably does that, ...

3

O(1) space, O(n) time As kinda pointed out already, your lists of nodes/values of the current level are up to $O(2^n)$ large. So your large memory usage of 150 MB is no wonder. It could easily be much more. LeetCode must have only very shallow trees (Yeah just checked, max height is only 22. Sigh). Here's somewhat the other extreme, taking only O(1) extra ...

3

It would also be easier if we follow TDD - Test Driven Development. We build the boiler plate that LeetCode is building for you. from __future__ import annotations import dataclasses from typing import Any, Optional @dataclasses.dataclass class Node: val: Any left: Optional[Node] = None right: Optional[Node] = None We get a tree with only one ...

2

Fix compiler warnings The compiler will warn about some unused parameters and of comparisons between integers of different signedness. For the latter, the solution is simple; instead of: for (auto i = 0; i < some.size(); i++) { Write the type of k explicitly: for (size_t i = 0; i < some.size(); i++) { The unused parameters of build_tree() should be ...

2

What you're essentially doing with your binary tree is checking all possible combinations of numbers from the list [i^n | i <- [1..x]]. That's quite a lot of combinations! (Exercise: how many?) Not all of those combinations are sensible, however. For example, if x = 100 and n = 2, and you've already chosen, say, 4 and 5 (giving 62+72=85), then adding 82=...

1

Thank you for the suggestions everyone. I was able to figure out the lapse in my initial judgement, and I was able to think of a solution that works, and I was able to implement it as well (after some hiccups and minor modifications along the way). Here's what I got: def isSymmetric(self,root): if root == None: return True else: ...

Only top voted, non community-wiki answers of a minimum length are eligible