🎨Now live: Try our Free AI Image Generation Feature

Description
The problem is to perform a postorder traversal on a binary tree. In a postorder traversal, the nodes are visited in the following order: left subtree, right subtree, and then the root node. The task is to return a list of node values in the order they are visited during the traversal.
Intuition
Postorder traversal can be seen as a bottom-up approach to tree traversal. It is intuitive because it processes all child nodes before processing the parent node, which is often useful in scenarios where a node's state depends on the states of its children. The recursive nature of trees makes recursion a natural fit for this traversal.
Approach
- Recursive Function:
- Create a helper function
traverse
that takes the current node and a listresult
as arguments. - If the current node isnull
, return immediately. - Recursively call thetraverse
function on the left child, followed by the right child. - After both children have been processed, add the current node's value to theresult
list. - Initialization:
- Start by initializing an empty list
result
that will store the node values in postorder. - Call thetraverse
function with the root of the tree and the listresult
. - Finally, return the listresult
which contains the postorder traversal of the tree.
Complexity
Time Complexity:
(O(N)), where (N) is the number of nodes in the tree. Each node is visited exactly once during the traversal.
Space Complexity:
- Recursive Call Stack: (O(H)), where (H) is the height of the tree. In the worst case, the height could be (O(N)) for a skewed tree.
- Auxiliary Space:(O(N)) for storing the result list
result
, which contains the node values.
Code
C++
class Solution {
public:
void traverse(TreeNode* node, std::vector& result) {
if (node == nullptr)
return;
traverse(node->left, result);
traverse(node->right, result);
result.push_back(node->val);
}
std::vector postorderTraversal(TreeNode* root) {
std::vector result;
traverse(root, result);
return result;
}
};
Python
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
class Solution:
def traverse(self, node, result):
if not node:
return
self.traverse(node.left, result)
self.traverse(node.right, result)
result.append(node.val)
def postorderTraversal(self, root):
result = []
self.traverse(root, result)
return result
Java
class Solution {
private void traverse(TreeNode node, List result) {
if (node == null)
return;
traverse(node.left, result);
traverse(node.right, result);
result.add(node.val);
}
public List postorderTraversal(TreeNode root) {
List result = new ArrayList<>();
traverse(root, result);
return result;
}
}
JavaScript
var postorderTraversal = function(root) {
let result = [];
function traverse(node)
{
if(node === null)
return 0;
traverse(node.left);
traverse(node.right);
result.push(node.val);
}
traverse(root);
return result;
};