二叉树 前序遍历

Question

1、递归前序

static void preOrder(Node T) {
  if (T == null)
    return;
  System.out.print(T.val + " ");
  preOrder(T.left);
  preOrder(T.right);
}

2、非递归前序

前序遍历顺序为: 根结点->左子树->右子树，所以对于正在访问的根结点，可以直接访问，访问完之后，按照相同的方式访问左子树，再访问右子树，过程如下 ：

• 如果当前节点 p 不为空，访问结点 p ，并将结点 p 入栈，并继续访问左子树（直到左子树为空)；
• 否则将栈顶元素出栈，并访问栈顶的元素的右子树；
• 直到栈为空且 p 为空，循环结束。

static void iterativePre(Node root) {
  Stack<Node> s = new Stack<>();
  Node p = root;
  while (!s.empty() || p != null) {
    if (p != null) {//也可以写一个 while 循环，直到左子树为空
      s.push(p);
      System.out.print(p.val + " ");
      p = p.left;
    } else {
      p = s.pop();
      p = p.right;
    }
  }
}

也可以将上面的一直访问到左子树为空写成一个 while 循环：

static void iterativePre2(Node root) {
  Stack<Node> s = new Stack<>();
  Node p = root;
  while (!s.empty() || p != null) {
    while (p != null) { // while 循环，直到左子树为空
      s.push(p);
      System.out.print(p.val + " ");
      p = p.left;
    }
    p = s.pop();
    p = p.right;
  }
}

还有另外一种写法是：

• 先把根节点入栈，然后每次出栈一个元素，先访问这个元素，然后如果它的右子树存在，就入栈，如果它的左子树存在也入栈；
• 为什么要先入右子树呢，因为，前序遍历是中->左->右，而栈可以逆序，所以先右再左；

这个方法在后续遍历的双栈法中有体现，那个只是这个稍微的修改。

static void iterativePre3(Node root) {
  if (root == null)
    return;
  Node p = root;
  Stack<Node> stack = new Stack<>();
  stack.add(p);
  while (!stack.isEmpty()) {
    p = stack.pop();
    System.out.print(p.val + " ");
    if (p.right != null)// 先右再左即可
      stack.push(p.right);
    if (p.left != null)
      stack.push(p.left);
  }
}