145. Binary Tree Postorder Traversal
Last updated
Last updated
// Definition for a binary tree node.
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode() {}
TreeNode(int val) { this.val = val; }
TreeNode(int val, TreeNode left, TreeNode right) {
this.val = val;
this.left = left;
this.right = right;
}
}/**
* Time complexity : O(N), where N is the number of nodes. We visit each
* node exactly once, thus the time complexity is O(N).
* Space complexity : up to O(H) to keep the recursion stack,
* where H is a tree height.
*/
class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
LinkedList<Integer> result = new LinkedList();
helper(root, result);
return result;
}
private void helper(TreeNode node, LinkedList<Integer> result) {
if(node == null) return;
helper(node.left, result);
helper(node.right, result);
result.add(node.val);
}
}/**
* Time complexity :
* Space complexity :
*/
class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> resultList = new LinkedList();
Stack<TreeNode> s = new Stack();
TreeNode curr = root;
while(!s.isEmpty() || curr != null) {
if(curr != null) {
s.push(curr);
curr = curr.left;
} else {
TreeNode temp = s.peek().right;
if(temp == null) {
temp = s.pop();
resultList.add(temp.val);
while(!s.isEmpty() && temp == s.peek().right) {
temp = s.pop();
resultList.add(temp.val);
}
} else {
curr = temp;
}
}
}
return resultList;
}
}/**
* Time complexity : O(N), where N is the number of nodes. We visit each
* node exactly once, thus the time complexity is O(N).
* Space complexity : up to O(H) to keep the stack, where H is a tree height.
*/
class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
LinkedList<Integer> result = new LinkedList();
if(root == null) return result;
Stack<TreeNode> stack = new Stack();
stack.add(root);
while(!stack.isEmpty()) {
root = stack.pop();
result.addFirst(root.val);
if(root.left != null) stack.push(root.left);
if(root.right != null) stack.push(root.right);
}
return result;
}
}