Given a binary tree, return the post-order traversal of its nodes’ values.
For traversing a binary tree in post-order fashion, we must do these three things for every node N starting from root node of the tree: (L) Recursively traverse its left subtree. When this step is finished we are back at N again. (R) Recursively traverse its right subtree. When this step is finished we are back at N again. (N) Process N itself
In normal post-order traversal we visit left subtree before the right subtree. If we visit right subtree before visiting the left subtree, it is referred as reverse post-order traversal.
Example:
As we can see before processing any node, the left subtree is processed first, followed by the right subtree and the node is processed at last. These operations can be defined recursively for each node. The recursive implementation is referred to as depth-first search(DFS), as the search tree is deepened as much as possible on each child before going to the next sibling.
Solution
We can use recurrsion to traverse PostOrder.
Code
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 |
/* public class TreeNode { public int val; public TreeNode left; public TreeNode right; public TreeNode(int x) { val = x; } } */ public class PostOrderTraversal { public static void main(String[] args) { TreeNode root1 = new TreeNode(1); TreeNode root2 = new TreeNode(2); TreeNode root3 = new TreeNode(3); TreeNode root4 = new TreeNode(4); TreeNode root5 = new TreeNode(5); root1.left = root2; root1.right = root3; root2.left = root4; root2.right = root5; postOrderTrav(root1); } public static void postOrderTrav(TreeNode a) { if (a == null) return; postOrderTrav(a.left); postOrderTrav(a.right); System.out.print(a.val+" "); } } |
Output
We encourage you to write a comment if you have a better solution or having any doubt on the above topic.