Description
Given the root of a binary tree, return the postorder traversal of its nodes’ values.
Examples:
Example 1:
Input: root = [1,null,2,3]
Output: [3,2,1]
Example 2:
Input: root = []
Output: []
Example 3:
Input: root = [1]
Output: [1]Solution in Python
To solve the problem of postorder traversal of a binary tree in Python, we’ll follow these steps:
- Postorder Traversal Definition: In postorder traversal, the nodes are visited in the order: left subtree, right subtree, and then the root node.
- Recursive Approach: We can achieve this traversal using recursion. We’ll recursively traverse the left subtree, then the right subtree, and finally visit the root node.
Python
class Solution:
def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
def traverse(node):
# Base case: if the node is None, return an empty list
if not node:
return []
# Recurse on the left subtree
left = traverse(node.left)
# Recurse on the right subtree
right = traverse(node.right)
# Visit the root node (current node)
return left + right + [node.val]
# Start the traversal from the root
return traverse(root)Detailed Explanation:
- TreeNode Definition:
- The
TreeNodeclass represents a node in a binary tree with a value (val), a left child (left), and a right child (right).
- The
- Solution Class and Method:
- The
Solutionclass contains thepostorderTraversalmethod which will be called to get the postorder traversal of the tree.
- The
- Recursive Traverse Function:
- Inside the
postorderTraversalmethod, we define a nested functiontraverse(node). - Base Case: If the
nodeisNone(i.e., the tree is empty or we’ve reached a leaf’s child), return an empty list. - Recursive Case:
- Traverse the left subtree by calling
traverse(node.left). - Traverse the right subtree by calling
traverse(node.right). - Visit the current node by adding
node.valto the result.
- Traverse the left subtree by calling
- The final result for each node is the concatenation of the left subtree result, right subtree result, and the current node’s value in that order.
- Inside the
- Start Traversal:
- Call the
traversefunction with therootnode and return its result.
- Call the
This implementation ensures that we traverse the tree in postorder and collect the values of the nodes as required.
Solution in Javascript
JavaScript
/**
* @param {TreeNode} root
* @return {number[]}
*/
var postorderTraversal = function(root) {
// Helper function to perform the postorder traversal
const traverse = (node) => {
// Base case: if the node is null, return an empty array
if (!node) {
return [];
}
// Recursively traverse the left subtree
const left = traverse(node.left);
// Recursively traverse the right subtree
const right = traverse(node.right);
// Visit the root node (current node)
// Combine the results from left, right and current node in postorder manner
return left.concat(right, node.val);
};
// Start the traversal from the root
return traverse(root);
};Solution in Java
Java
import java.util.ArrayList;
import java.util.List;
class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
// List to store the result of the traversal
List<Integer> result = new ArrayList<>();
// Helper method to perform the traversal
postorderHelper(root, result);
// Return the result list
return result;
}
// Helper method for postorder traversal
private void postorderHelper(TreeNode node, List<Integer> result) {
// Base case: if the node is null, return
if (node == null) {
return;
}
// Recursively traverse the left subtree
postorderHelper(node.left, result);
// Recursively traverse the right subtree
postorderHelper(node.right, result);
// Visit the current node (add its value to the result list)
result.add(node.val);
}
}Solution in C#
C#
using System.Collections.Generic;
public class Solution {
// Main method to initiate postorder traversal
public IList<int> PostorderTraversal(TreeNode root) {
// List to store the result of the traversal
IList<int> result = new List<int>();
// Helper method to perform the traversal
PostorderHelper(root, result);
// Return the result list
return result;
}
// Helper method for postorder traversal
private void PostorderHelper(TreeNode node, IList<int> result) {
// Base case: if the node is null, return
if (node == null) {
return;
}
// Recursively traverse the left subtree
PostorderHelper(node.left, result);
// Recursively traverse the right subtree
PostorderHelper(node.right, result);
// Visit the current node (add its value to the result list)
result.Add(node.val);
}
}