P65 二叉树前序遍历

描述#

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

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

/ 

2   3


4
/
5
你要返回的前序遍历结果是：
1, 2, 4, 5, 3

代码#

public class AlgoCasts {

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

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

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

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

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

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

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

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

}