145. Binary Tree Postorder Traversal — LeetCode(Python)
I got you!
Problem:
Given the root of a binary tree, return the postorder traversal of its nodes' values.
Example 1:
Input: root = [1,null,2,3]
Output: [3,2,1]Example 2:
Input: root = []
Output: []Example 3:
Input: root = [1]
Output: [1]Constraints:
- The number of the nodes in the tree is in the range
[0, 100]. -100 <= Node.val <= 100
Follow up: Recursive solution is trivial, could you do it iteratively?
Solution:
1. Recursive —
Explanation —
We can solve this problem very easily using recursion.
We use a helper function for our depth first search (DFS) algorithm.
The base case of the recursive function is when we reach a NULL node, in which case we return None.
Since this is a preorder traversal, the value of the root node needs to be stored after the left child’s value and the right child’s value.
So, we append root.val to our answer ans after recursing on the left and right subtrees.
Recursion takes care of the rest and we just need to take the recursive leap of faith.
Finally, we return ans.
Time and Space Complexity —
Since we are visiting all nodes a constant number of times, we can say that our algorithm runs in linear time.
Also, the recursion stack might be storing all nodes in the tree in a really skewed tree (like a linked list), so we can say that we require a linear amount of auxiliary space.
Thus, if there are n nodes in the binary tree,
Time Complexity: O(n)
Space Complexity: O(n)
2. Iterative —
Explanation —
We can use the fact that we need to traverse a node twice — once before we go to it’s left subtree and once after we are done traversing the left subtree.
We keep track of whether a node is visited or not.
So we instead of storing only a node in our stack, we also store a boolean value True/False to represent it’s visited status.
As we iterate through the tree, we keep adding nodes and visited values as a tuple in our stack.
We start by adding the root node with a value False since it has not yet been visited.
Note: We assume a node to be visited when it has been popped out from the stack and not when it is pushed onto the stack.
We now keep popping from the stack.
If the current node is not a NULL node, then we check if it has been visited. If yes, then we append it to our answer. If not, then we append the nodes in the following order:
root → right → left
This time, we change the visited status of our current node to be True.
The while loop terminates when the stack is empty and we have traversed all nodes in the tree. This is when we return our path ans.
Time and Space Complexity —
The complexity analysis is the same as that of Solution 2 above.
Since we are visiting every node in the tree a constant number of time, we can say that our algorithm requires a linear amount of time to run.
Also, our stack might be storing all nodes in the tree is the tree is really skewed (like a linked list). So we must assume that we require linear amount of extra space in the worst case.
Thus, if there are n nodes in the binary tree,
Time Complexity: O(n)
Space Complexity: O(n)
