树的遍历

树的遍历分为四种：前序遍历，中序遍历，后序遍历，层序遍历。

        A
       / \
      B   C
     /\  /\
     D E F G
        \
         H

前序遍历：前序遍历的遍历顺序是 根→左→右的顺序打印，我们先打印根节点，在打印左孩子，最后打印右孩子，如上图，我们先打印A，然后打印B，发现B也有左孩子，之后我们以B为根节点再进行一次跟左右遍历，打印D，之后我们准备打印B的右孩子就是E，发现E有右孩子，所以我们这边又以E作为根节点，进行跟左右操作，以此类推，得到最后的结果是：ABDEHCFG。

中序遍历：先序遍历的遍历顺序是 左→根→右的顺序打印，我们一开始准备打印A的左孩子B，发现B也有左孩子然后以B为根节点进行左→根→右进行打印，所以我们一开始打印的是D这个节点，中序遍历和先序遍历的思维差不多，无非就是打印顺序的调整。最后的结果为：DBEHAFCG。

后序遍历：先序遍历的遍历顺序是 左→右→根的顺序打印，跟前面两种遍历方式类似，就是打印的顺序不同，我们应该先遍历完左右孩子再进行根节点的打印。最后的结果是：DHEBFGCA。

层序遍历：层序遍历就比较简单，层序遍历就是按照各层顺序打印结果，如上图的层序遍历就是：ABCDEFGH。

前中后遍历，均可以使用递归或迭代的方式进行。层序遍历一般使用迭代来实现。

1. 递归方式

   // 前序遍历
   void preOrderTraversal(TreeNode root) {
       if (root == null) {
           return;
       } else {
           System.out.print(root.val + " ");
           preOrderTraversal(root.left);
           preOrderTraversal(root.right);
       }
   }
   // 中序遍历
   void inOrderTraversal(TreeNode root) {
       if (root == null) {
           return;
       } else {
           inOrderTraversal(root.left);
           System.out.print(root.val + " ");
           inOrderTraversal(root.right);
       }
   }
   //后序遍历
   void poseOrderTraversal(TreeNode root) {
       if (root == null) {
           return;
       } else {
           poseOrderTraversal(root.left);
           poseOrderTraversal(root.right);
           System.out.print(root.val + " ");
       }
   }

2. 迭代方式（需要使用栈来辅助进行）

   // 非递归的前序遍历
   void preOrderTraversalNor(TreeNode root) {
       if (root == null) {
           return;
       }
       Stack<TreeNode> stack = new Stack<>();
       TreeNode cur = root;
       while (cur != null || !stack.empty()) {
           while (cur != null) {
               stack.push(cur);
               System.out.print(cur.val + " ");
               cur = cur.left;
           }
           TreeNode top = stack.pop();
           cur = top.right;
       }
   }
   // 非递归的中序遍历
   void inOrderTraversalNor(TreeNode root) {
       if (root == null) {
           return;
       }
       Stack<TreeNode> stack = new Stack<>();
       TreeNode cur = root;
       while (cur != null || !stack.empty()) {
           while (cur != null) {
               stack.push(cur);
               cur = cur.left;
           }
           TreeNode top = stack.pop();
           System.out.print(top.val + " ");
           cur = top.right;
       }
   }
   // 非递归的后序遍历
   void poseOrderTraversalNor(TreeNode root) {
       if (root == null) {
           return;
       }
       Stack<TreeNode> stack = new Stack<>();
       TreeNode pre = null;
       TreeNode cur = root;
       while (cur != null || !stack.empty()) {
           while (cur != null) {
               stack.push(cur);
               cur = cur.left;
           }
           cur = stack.peek();
           if (cur.right == null||pre==cur.right) {
               TreeNode top = stack.pop();
               System.out.print(top.val+ " ");
               pre=cur;
               cur=null;
           } else {
               cur=cur.right;
           }
       }
   }
   
   // 层序遍历
   void levelOderTraversal(TreeNode root) {
       Queue<TreeNode> q1 = new LinkedList<>();
       if (root == null) {
           return;
       }
       q1.offer(root);
       while (!q1.isEmpty()) {
           TreeNode top = q1.poll();
           System.out.print(top.val + " ");
           if (top.left != null) {
               q1.offer(top.left);
           }
           if (top.right != null) {
               q1.offer(top.right);
           }
       }
       System.out.println();
   }

   为什么采用“栈”：

   来看二叉树的前序遍历的特点，先遍历根节点，如果根节点存在左子树，则先遍历左子树，再遍历右子树。而对于左子树，也是同样的遍历方式，先遍历该左子树的根节点，再遍历该左子树的左子树，再遍历该左子树的右子树。也即，一直遍历到最左下。遍历到最左下的时候，如果最左下节点无右子树，则需要回溯到它的父节点，以相同的方式遍历右子树。

   在这个回溯的过程中，我们需要能够知道上一个最近访问的节点是哪个，根据这个特点，我们很容易想到Stack，也就是栈的特点。栈就是一个后进先出的数据结构，因此，在非递归中采用栈来保存遍历过的节点。