Dare2Solve
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.
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.
Recursive Function:
traverse
that takes the current node and a list result
as arguments.null
, return immediately.traverse
function on the left child, followed by the right child.result
list.Initialization:
result
that will store the node values in postorder.traverse
function with the root of the tree and the list result
.result
which contains the postorder traversal of the tree.(O(N)), where (N) is the number of nodes in the tree. Each node is visited exactly once during the traversal.
result
, which contains the node values.class Solution {
public:
void traverse(TreeNode* node, std::vector<int>& result) {
if (node == nullptr)
return;
traverse(node->left, result);
traverse(node->right, result);
result.push_back(node->val);
}
std::vector<int> postorderTraversal(TreeNode* root) {
std::vector<int> result;
traverse(root, result);
return result;
}
};
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
class Solution {
private void traverse(TreeNode node, List<Integer> result) {
if (node == null)
return;
traverse(node.left, result);
traverse(node.right, result);
result.add(node.val);
}
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<>();
traverse(root, result);
return result;
}
}
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;
};