前序遍历

前序遍历（头左右）：A -> B -> D -> F -> G -> H -> I -> E -> C

前序遍历（递归） #

public static void pre(Node head) {
  if (head == null) return;
  System.out.print(head.value + " ");
  pre(head.left);
  pre(head.right);
}

前序遍历（非递归 单栈） #

public static void pre(Node head) {
  System.out.print("pre-order: ");
  if (head != null) {
    Stack<Node> stack = new Stack<>();
    stack.push(head);
    while (!stack.isEmpty()) {
      head = stack.pop();
      System.out.print(head.value + " ");
      if (head.right != null)
        stack.push(head.right);
      if (head.left != null)
        stack.push(head.left);
    }
  }
  System.out.println();
}