leetcode 145 binary tree postorder traversal

Given a binary tree, return the postorder traversal of its nodes’ values.

Example:

1
2
3
4
5
6
7
8
Input: [1,null,2,3]
1

2
/
3

Output: [3,2,1]

Follow up: Recursive solution is trivial, could you do it iteratively?


Recursive one is trivia:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class  {
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> ans = new LinkedList<>();
traversal(ans, root);
return ans;
}

public void traversal(List<Integer> ans, TreeNode root) {
if (root == null) {
return ;
}
traversal(ans, root.right);
traversal(ans, root.left);
ans.add(root.val);
}
}

For iterative one, it’s a little complicated,

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class  {
public List<Integer> postorderTraversal(TreeNode root) {
LinkedList<Integer> ans = new LinkedList<>();
if (root == null) return ans;
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
while(!stack.isEmpty()) {
TreeNode p = stack.pop();
ans.addFirst(p.val);
if (p.left != null) {
stack.push(p.left);
}
if (p.right!=null) {
stack.push(p.right);
}
}
return ans;
}
}

Expansions:

Preorder Traversal

Recursive one:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class  {
public List<Integer> preorderTravesl(TreeNode root) {
LinkedList<Integer> ans = new LinkedList<>();
travel(ans, root);
return ans;
}
public void travel(List<Integer> ans, TreeNode root) {
if (root == null) {
return ;
}
ans.add(root.val);
travel(ans, root.left);
travel(ans, root.right);
}
}

Iterative one:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class  {
public List<Integer> preorderTravesl(TreeNode root) {
LinkedList<Integer> ans = new LinkedList<>();
if (root == null) return ans;
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
while (!stack.isEmpty()) {
TreeNode p = stack.pop();
ans.add(p.val);
if (p.right != null) {
stack.push(p.right);
}
if (p.left != null) {
stack.push(p.left);
}
}
return ans;
}
}

Inorder Traversal

Recurative One:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class  {
public List<Integer> inorderTravesl(TreeNode root) {
LinkedList<Integer> ans = new LinkedList<>();
travel(ans, root);
return ans;
}
public void travel(List<Integer> ans, TreeNode root) {
if (root == null) {
return ;
}
travel(ans, root.left);
ans.add(root.val);
travel(ans, root.right);
}
}

Iterative One:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public List<Integer> preorderTravesl(TreeNode root) {
LinkedList<Integer> ans = new LinkedList<>();
if (root == null) return ans;
TreeNode p = root;
Stack<TreeNode> stack = new Stack<>();
while (!stack.isEmpty() || p != null) {
while (p != null) {
stack.push(p);
p = p.left;
}
p = stack.pop();
ans.add(p.val);
p = p.right;
}
return ans;
}
}