二叉树的遍历

树是一种经常用到的结构，用来模拟具有树状结构性质的数据集合

树的每一个节点有一个值和一个包含所有子节点的列表，从图的观点来看，树也可视为一个拥有N 个节点和N-1 条边的一个有向无环图。

二叉树是一种更为典型的树状结构。如它名字所描述的那样，二叉树是每个节点最多有两个子树的树结构，通常子树被称作“左子树”和“右子树”。

树的遍历

• 前序遍历

首先访问根节点，然后遍历左子树，最后遍历右子树

      F
    /   \
   B      G
  / \       \
 A   D       I
    / \     / 
  C    E   H
//遍历结构是 
F、B、A、D、C、E、G、I、H

• 中序遍历

先遍历左子树，然后访问根节点，最后访问右子树

      F
    /   \
   B      G
  / \       \
 A   D       I
    / \     / 
  C    E   H
//遍历结构是 
A、B、C、D、E、F、G、H、I

• 后序遍历

先遍历左子树，然后遍历右子树，最后访问根节点

      F
    /   \
   B      G
  / \       \
 A   D       I
    / \     / 
  C    E   H
//遍历结构是 
A、C、E、D、B、H、I、G、F

总结

所谓前中后都是根据根节点的位置来命名的。后序在数学表达式中广泛使用，编写程序来解析后缀法更加容易。

这里举一个例子：

对于这个图，我们使用中序遍历很容易能找出表达式：4x(7-2)+5

如果你想对这棵树进行后序遍历，使用栈来处理表达式会变得更加容易。 每遇到一个操作符，就可以从栈中弹出栈顶的两个元素，计算并将结果返回到栈中。

遍历

我们有三种常用的遍历方法、递归、迭代、morris，我们以给定的节点类如下，分别介绍三种遍历方法

 public class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode() {}
      TreeNode(int val) { this.val = val; }
      TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
          this.left = left;
          this.right = right;
      }
  }

• 递归

  //递归逻辑是最简单的，我们只需要把输出加在不同的位置
  public static void order(TreeNode tree) {
      if (tree == null)
          return;
        //前序写法，取消下面代码注释
      // System.out.printf(tree.val + "");
        //然后输出左节点
      preOrder(tree.left);
        //前序写法，取消下面代码注释
      // System.out.printf(tree.val + "");
        //然后输出右节点
      preOrder(tree.right);
      //后序写法，取消下面代码注释
      // System.out.printf(tree.val + "");
  }
  

• 迭代

  本质上是在模拟递归，因为在递归的过程中使用了系统栈，所以在迭代的解法中常用 Stack 来模拟系统栈。

  • 前序

    首先我们应该创建一个Stack 用来存放节点，首先我们想要打印根节点的数据，此时 Stack里面的内容为空，所以我们优先将头结点加入Stack，然后打印。

    之后我们应该先打印左子树，然后右子树。所以先加入 Stack 的就是右子树，然后左子树。
    此时你能得到的流程如下:

    

```java
public static void preOrderIteration(TreeNode head) {
    if (head == null) {
        return;
    }
    Stack<TreeNode> stack = new Stack<>();
    stack.push(head);
    while (!stack.isEmpty()) {
        TreeNode node = stack.pop();
        System.out.print(node.value + " ");
        if (node.right != null) {
            stack.push(node.right);
        }
        if (node.left != null) {
            stack.push(node.left);
        }
    }
}
```

• 中序

  1. 同理创建一个 Stack，然后按 左 中 右的顺序输出节点。
  2. 尽可能的将这个节点的左子树压入 Stack，此时栈顶的元素是最左侧的元素，其目的是找到一个最小单位的子树(也就是最左侧的一个节点)，并且在寻找的过程中记录了来源，才能返回上层,同时在返回上层的时候已经处理完毕左子树了。。
  3. 当处理完最小单位的子树时，返回到上层处理了中间节点。（如果把整个左中右的遍历都理解成子树的话，就是处理完 左子树->中间(就是一个节点)->右子树）
  4. 如果有右节点，其也要进行中序遍历。

当整个左子树退栈的时候这个时候输出了该子树的根节点 2，之后输出中间节点 1。然后处理根节点为3右子树。

```java
public static void inOrderIteration(TreeNode head) {
    if (head == null) {
        return;
    }
    TreeNode cur = head;
    Stack<TreeNode> stack = new Stack<>();
    while (!stack.isEmpty() || cur != null) {
        while (cur != null) {
            stack.push(cur);
            cur = cur.left;
        }
        TreeNode node = stack.pop();
        System.out.print(node.value + " ");
        if (node.right != null) {
            cur = node.right;
        }
    }
}
```

• 后序

  //1 前序遍历的过程 是 中左右。
  //2 将其转化成 中右左。也就是压栈的过程中优先压入左子树，在压入右子树。
  //3 然后将这个结果返回来，这里是利用栈的先进后出倒序打印。
  public static void postOrderIteration(TreeNode head) {
          if (head == null) {
              return;
          }
          Stack<TreeNode> stack1 = new Stack<>();
          Stack<TreeNode> stack2 = new Stack<>();
          stack1.push(head);
          while (!stack1.isEmpty()) {
              TreeNode node = stack1.pop();
              stack2.push(node);
              if (node.left != null) {
                  stack1.push(node.left);
              }
              if (node.right != null) {
                  stack1.push(node.right);
              }
          }
          while (!stack2.isEmpty()) {
              System.out.print(stack2.pop().value + " ");
          }
      }
  

  //1 用一个指针 cur 标记当前退出的节点是什么。
  //2 后序遍历的过程中在遍历完左子树跟右子树 cur 都会回到根结点。所以当前不管是从左子树还是右子树回到根结点都不应该再操作了，应该退回上层。
  //3 如果是从右边再返回根结点，应该回到上层。
  
  public static void postOrderIteration2(TreeNode head) {
      if (head == null) {
          return;
      }
      TreeNode cur = head;
      Stack<TreeNode> stack = new Stack<>();
      stack.push(head);
      while (!stack.isEmpty()) {
          TreeNode peek = stack.peek();
          if (peek.left != null && peek.left != cur && peek.right != cur) {
              stack.push(peek.left);
          } else if (peek.right != null && peek.right != cur) {
              stack.push(peek.right);
          } else {
              System.out.print(stack.pop().val + " ");
              cur = peek;
          }
      }
  }
  

• Morris解法

  Morris 遍历使用二叉树节点中大量指向 null 的指针，由 Joseph Morris 于 1979 年发明。
  时间复杂度：
  额外空间复杂度：

  在你阅读以下代码之前，在这边先讲解一下 Morris 的通用解法过程。

Morris 的整体思路就是将 以某个根结点开始，找到它左子树的最右侧节点之后与这个根结点进行连接
我们可以从 图2 看到，如果这么连接之后，cur 这个指针是可以完整的从一个节点顺着下一个节点遍历，将整棵树遍历完毕，直到 7 这个节点右侧没有指向。

public static void preOrderMorris(TreeNode head) {
  if (head == null) {
      return;
  }
  TreeNode cur1 = head;//当前开始遍历的节点
  TreeNode cur2 = null;//记录当前结点的左子树
  while (cur1 != null) {
      cur2 = cur1.left;
      if (cur2 != null) {
          while (cur2.right != null && cur2.right != cur1) {//找到当前左子树的最右侧节点，且这个节点应该在指向根结点之前，否则整个节点又回到了根结点。
              cur2 = cur2.right;
          }
          if (cur2.right == null) {//这个时候如果最右侧这个节点的右指针没有指向根结点，创建连接然后往下一个左子树的根结点进行连接操作。
              cur2.right = cur1;
              cur1 = cur1.left;
              continue;
          } else {//当左子树的最右侧节点有指向根结点，此时说明我们已经回到了根结点并重复了之前的操作，同时在回到根结点的时候我们应该已经处理完 左子树的最右侧节点 了，把路断开。
              cur2.right = null;
          }
      } 
      cur1 = cur1.right;//一直往右边走，参考图
  }
}

• 前序遍历

  1. 在某个根结点创建连线的时候打印。因为我们是顺着左边的根节点来创建连线，且创建的过程只有一次。
  2. 打印某些自身无法创建连线的节点，也就是叶子节点。

  public static void preOrderMorris(TreeNode head) {
      if (head == null) {
          return;
      }
      TreeNode cur1 = head;
      TreeNode cur2 = null;
      while (cur1 != null) {
          cur2 = cur1.left;
          if (cur2 != null) {
              while (cur2.right != null && cur2.right != cur1) {
                  cur2 = cur2.right;
              }
              if (cur2.right == null) {
                  cur2.right = cur1;
                  System.out.print(cur1.value + " ");
                  cur1 = cur1.left;
                  continue;
              } else {
                  cur2.right = null;
              }
          } else {
              System.out.print(cur1.value + " ");
          }
          cur1 = cur1.right;
      }
  }
  

• 中序遍历

  从最左侧开始顺着右节点打印。也就是在将 cu1 切换到上层节点的时候。

  public static void inOrderMorris(TreeNode head) {
      if (head == null) {
          return;
      }
      TreeNode cur1 = head;
      TreeNode cur2 = null;
      while (cur1 != null) {
          cur2 = cur1.left;
          //构建连接线
          if (cur2 != null) {
              while (cur2.right != null && cur2.right != cur1) {
                  cur2 = cur2.right;
              }
              if (cur2.right == null) {
                  cur2.right = cur1;
                  cur1 = cur1.left;
                  continue;
              } else {
                  cur2.right = null;
              }
          }
          System.out.print(cur1.value + " ");
          cur1 = cur1.right;
      }
  }
  

• 后序遍历

当我们到达最左侧，也就是左边连线已经创建完毕了。
打印 4
打印 5 2
打印 6
打印 7 3 1
我们将一个节点的连续右节点当成一个单链表来看待。
当我们返回上层之后，也就是将连线断开的时候，打印下层的单链表。
比如返回到　２，此时打印　４
比如返回到　１，此时打印　５　２
比如返回到　３，此时打印　６
那么我们只需要将这个单链表逆序打印就行了，下文也给出了 单链表逆序代码
这里不应该打印当前层，而是下一层，否则根结点会先与右边打印。

public static void postOrderMorris(TreeNode head) {
  if (head == null) {
      return;
  }
  TreeNode cur1 = head;//遍历树的指针变量
  TreeNode cur2 = null;//当前子树的最右节点
  while (cur1 != null) {
      cur2 = cur1.left;
      if (cur2 != null) {
          while (cur2.right != null && cur2.right != cur1) {
              cur2 = cur2.right;
          }
          if (cur2.right == null) {
              cur2.right = cur1;
              cur1 = cur1.left;
              continue;
          } else {
              cur2.right = null;
              postMorrisPrint(cur1.left);
          }
      }
      cur1 = cur1.right;
  }
  postMorrisPrint(head);
}
//打印函数
public static void postMorrisPrint(TreeNode head) {
  TreeNode reverseList = postMorrisReverseList(head);
  TreeNode cur = reverseList;
  while (cur != null) {
      System.out.print(cur.value + " ");
      cur = cur.right;
  }
  postMorrisReverseList(reverseList);
}
//翻转单链表
public static TreeNode postMorrisReverseList(TreeNode head) {
  TreeNode cur = head;
  TreeNode pre = null;
  while (cur != null) {
      TreeNode next = cur.right;
      cur.right = pre;
      pre = cur;
      cur = next;
  }
  return pre;
}