leetcode 145 Binary Tree Postorder Traversal
z
 2019-03-31 20:01:53  

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 Solution {
    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 Solution {
		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 Solution {
  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 Solution {
  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 Solution {
  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;
  }
}