454. Post-Order Walk
A file system is modelled as a binary tree in root. To free disk space, a cleanup tool must delete the contents of a folder's left side, then its right side, and only then the folder itself.
Return the node values in post-order: all values of the left subtree first, then all values of the right subtree, and finally the value of the node itself. The result is an array with one entry per node; if the tree is empty return an empty array.
Example 1
- Input:
- root = [8,3,10,1,6]
- Output:
- [1,6,3,10,8]
- Explanation:
Left subtree gives 1, 6, 3; the right subtree is just 10; the root 8 comes last.
Example 2
- Input:
- root = [5,-2,null,4]
- Output:
- [4,-2,5]
- Explanation:
Node 4 is the left child of -2, so the order is 4, -2, then the root 5.
Constraints
0 ≤ number of nodes ≤ 105
-1000 ≤ node value ≤ 1000
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 1,200 msC++ 300 msJava 600 msJavaScript 600 msTypeScript 600 ms
Expected complexity
- Time
- O(n)
- Space
- O(h)