P172 二叉树后序遍历

描述#

这个题目说的是，给你一棵二叉树，你要返回一个序列，表示二叉树后序遍历的结果。

比如说，给你的二叉树是：
1
/ 

2   3


4
你要返回的后序遍历序列是：
[4, 2, 3, 1]

代码#

public class AlgoCasts {

  public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
      val = x;
    }
  }

  private void postorder(TreeNode root, List<Integer> result) {
    if (root == null) return;
    postorder(root.left, result);
    postorder(root.right, result);
    result.add(root.val);
  }

  // Time: O(n), Space: O(n)
  public List<Integer> postorderTraversalRecursive(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    postorder(root, result);
    return result;
  }

  // Time: O(n), Space: O(n)
  public List<Integer> postorderTraversalIterative(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    Stack<TreeNode> stack = new Stack<>();
    TreeNode pre = null;

    while (root != null || !stack.isEmpty()) {
      if (root != null) {
        stack.push(root);
        root = root.left;
      } else {
        root = stack.peek().right;
        if (root == null || root == pre) {
          pre = stack.pop();
          result.add(pre.val);
          root = null;
        }
      }
    }
    return result;
  }

  // Time: O(n), Space: O(n)
  public List<Integer> postorderTraversalIterative2(TreeNode root) {
    LinkedList<Integer> result = new LinkedList<>();
    if (root == null) return result;
    Stack<TreeNode> stack = new Stack<>();
    stack.push(root);

    while (!stack.isEmpty()) {
      TreeNode node = stack.pop();
      result.addFirst(node.val);
      if (node.left != null) stack.push(node.left);
      if (node.right != null) stack.push(node.right);
    }
    return result;
  }

}