1）递归：
public void midorder(Node p) { if(p == null) { return ; }else { this.midorder(p.left); System.out.print(p.val + " "); this.midorder(p.right); } }2）或许你会使用这样子的非递归 【在while循环中，直接while循环，这样不够有迭代的思想，同时有时候的问题需要逐步的走循环】
public void midorder02(Node p) { Deque<Node> s = new LinkedList<>(); if(p == null) { return ; } s.push(p); while(!s.isEmpty()) { while(s.peek().left != null) { Node node = s.peek().left; s.push(node); } Node node = s.peek().right; System.out.print(s.pop().val + " "); while(!s.isEmpty() && node == null) { node = s.peek().right; System.out.print(s.pop().val + " "); } if(node != null) { s.push(node); } } }3）推荐这种
public List<Integer> inOrder06(Node node) { LinkedList<Integer> list = new LinkedList<Integer>(); if(node == null) { return list; } Node p = node; // System.out.print(p.val + " "); // list.add(p.val); while(p != null) { if(p.left == null) { System.out.print(p.val + " "); list.add(p.val); p = p.right; }else { //使用的是if，而不是while，【逐步迭代】 Node p1 = p.left; while(p1.right != null && p1.right != p) { //先写的是p1.right != null， ！= p是后面补上的 p1 = p1.right; } if(p1.right == null) { //将节点连起来 p1.right = p; p = p.left; }else { //说明已经有了“环路” System.out.print(p.val + " "); list.add(p.val); p = p.right; } } } return list; }4)使用Morris
public List<Integer> inOrder09(Node node){ LinkedList<Integer> list = new LinkedList<Integer>(); if(node == null) { return list; } Node p = node; while(p != null) { if(p.left != null) { //找到最右边的节点 Node temp = p.left; while(temp.right != null && temp.right != p) { temp = temp.right; } if(temp.right == null) {//连接成环 temp.right = p; // System.out.print(p.val + " "); // list.add(p.val); p = p.left; }else { //本来就是环 System.out.print(p.val + " "); list.add(p.val); p = p.right; temp.right = null;//使得可以还原morris } }else { System.out.print(p.val + " "); list.add(p.val); p = p.right; } } return list; }完整示例：
package com.hhh.aa.basicTree02; import java.util.Deque; import java.util.LinkedList; import java.util.List; import java.util.Queue; import org.junit.Test; /** * 我的二叉树 【中序遍历】 * @author dell * */ public class TestMyTreeB021 { /** * 测试遍历二叉树的中序遍历【先输出节点的值】 * @param p */ public void midorder(Node p) { if(p == null) { return ; }else { this.midorder(p.left); System.out.print(p.val + " "); this.midorder(p.right); } } /** * 执行用时：10 ms, 在所有 Java 提交中击败了46.21% 的用户 内存消耗：36.7 MB, 在所有 Java 提交中击败了97.69% 的用户 执行用时：1 ms, 在所有 Java 提交中击败了46.21% 的用户 内存消耗：36.7 MB, 在所有 Java 提交中击败了96.71% 的用户 * @param p */ public void midorder02(Node p) { Deque<Node> s = new LinkedList<>(); if(p == null) { return ; } s.push(p); while(!s.isEmpty()) { while(s.peek().left != null) { Node node = s.peek().left; s.push(node); } Node node = s.peek().right; System.out.print(s.pop().val + " "); while(!s.isEmpty() && node == null) { node = s.peek().right; System.out.print(s.pop().val + " "); } if(node != null) { s.push(node); } } } /** * lc简洁 * * 执行用时：10 ms, 在所有 Java 提交中击败了46.06% 的用户 内存消耗：36.7 MB, 在所有 Java 提交中击败了97.19% 的用户 * @param p */ public void midorder03(Node p) { Deque<Node> s = new LinkedList<>(); if(p == null) { return ; } while(p != null || !s.isEmpty()) { while(p != null) { s.push(p); p = p.left; } p = s.pop(); System.out.print(p.val + " "); p = p.right; } } /** * 执行用时：10 ms, 在所有 Java 提交中击败了45.52% 的用户 内存消耗：36.9 MB, 在所有 Java 提交中击败了69.23% 的用户 * @param node * @return */ public List<Integer> inOrder06(Node node) { LinkedList<Integer> list = new LinkedList<Integer>(); if(node == null) { return list; } Node p = node; // System.out.print(p.val + " "); // list.add(p.val); while(p != null) { if(p.left == null) { System.out.print(p.val + " "); list.add(p.val); p = p.right; }else { //使用的是if，而不是while，【逐步迭代】 Node p1 = p.left; while(p1.right != null && p1.right != p) { //先写的是p1.right != null， ！= p是后面补上的 p1 = p1.right; } if(p1.right == null) { //将节点连起来 p1.right = p; p = p.left; }else { //说明已经有了“环路” System.out.print(p.val + " "); list.add(p.val); p = p.right; } } } return list; } /** * 非递归，book * @param node * @return */ public List<Integer> inOrder07(Node node) { LinkedList<Integer> list = new LinkedList<Integer>(); if(node == null) { return list; } Deque<Node> s = new LinkedList<>(); s.push(node); while(!s.isEmpty()) { Node p = s.peek(); if(p.left != null) { s.push(p.left); }else { //p节点的左边为null System.out.print(p.val + " "); list.add(p.val); //从栈中弹出 s.pop(); //只要右边为null while(p.right == null && !s.isEmpty()) { p = s.pop(); System.out.print(p.val + " "); list.add(p.val); } if(p.right != null) { //先看右边是否为null，而不是看栈，否则导致树的一遍都没有遍历到 s.push(p.right); }else { break; } } } return list; } /** * morris * @param node * @return */ public List<Integer> inOrder09(Node node){ LinkedList<Integer> list = new LinkedList<Integer>(); if(node == null) { return list; } Node p = node; while(p != null) { if(p.left != null) { //找到最右边的节点 Node temp = p.left; while(temp.right != null && temp.right != p) { temp = temp.right; } if(temp.right == null) {//连接成环 temp.right = p; // System.out.print(p.val + " "); // list.add(p.val); p = p.left; }else { //本来就是环 System.out.print(p.val + " "); list.add(p.val); p = p.right; temp.right = null;//使得可以还原morris } }else { System.out.print(p.val + " "); list.add(p.val); p = p.right; } } return list; } /** * 初始化一个tree * 类广度遍历 * @param a * @return */ public Node initTree(Integer[] a) { if(a == null || a.length == 0) { return null; } int t = 0; Node p = new Node(a[t]); //至少有一个元素 Queue<Node> q = new LinkedList<>(); q.offer(p); while(!q.isEmpty()) { Node node = q.poll(); if(t + 1 == a.length) { //先判断数组中是否还有下一个元素 return p; }else { t++; if(a[t] == null) { //若下一个元素为null，则不需要创建新的节点 node.left = null; }else { node.left = new Node(a[t]); q.offer(node.left); } } if(t + 1 == a.length) { return p; }else { t++; if(a[t] != null){ //上面的简写，a[t] == null，不需要再赋值 node.right = new Node(a[t]); q.offer(node.right); } } } return p; } @Test public void test02() { Integer[] a = new Integer[] {1, 2, 3, 4, 5, 9, 10, null, 6, 7, 8, null, null, null, 11}; Node p1 = this.initTree(a); System.out.println("使用递归的中序遍历"); this.midorder(p1); System.out.println(); System.out.println("不使用递归的中序遍历"); this.midorder02(p1); System.out.println(); System.out.println("不使用递归的中序遍历【lc简洁】"); this.midorder03(p1); System.out.println(); // System.out.println("使用morris实现中序遍历"); // List<Integer> list = this.inOrder06(p1); // System.out.println(); // System.out.println("输出list：" + list.toString()); System.out.println("使用非递归遍历"); List<Integer> list = this.inOrder07(p1); System.out.println(); System.out.println("输出list ：" + list.toString()); System.out.println("morris"); list = this.inOrder09(p1); System.out.println(); System.out.println("输出list ：" + list.toString()); } }