中序遍历代码 java,前序遍历Java
Morris中序遍历 二叉树的中序遍历更好的空间复杂度
二叉树的中序遍历
二叉树的中序遍历，遍历顺序是先从左子树开始，接下访问根节点，然后访问右子树，我自己为了方便记忆，就是想中序，就是下一个访问中间节点，也就是从左子树开始，接下来访问根节点。
一般中序遍历是递归或者非递归方式实现。非递归是用栈实现。递归有递归深度，栈也有栈空间，这两种方式的空间复杂度都是O(n)。
递归实现的中序遍历：
1 public static void InOrder(TreeNode root) {2 if (root == null) return;3 InOrder(root.left);4 System.out.println(root.val);5 InOrder(root.right);6 }非递归实现的中序遍历：
1 public static void InOrderByStack(TreeNode root) { 2 if (root == null) return; 3 Stack<TreeNode> stack = new Stack<>(); 4 while (!stack.isEmpty() || root != null) { 5 while (root != null) { 6 stack.push(root); 7 root = root.left; 8 } 9 root = stack.pop();10 System.out.println(root.val);11 root = root.right;12 }13 } 更好的空间复杂度因为中序遍历时候，每访问一个节点，不知道下一个节点是哪个，所以借助于递归和栈实现，导致空间复杂度是O(n)，而Morris中序遍历是，先去找节点的过程就已经把每个节点的下一个节点已经找到，做了牵线，所以依次遍历即可。
具体就是修改节点的right指针，使之指向下一个节点。如下图所示：
修改1节点的right指针指向4，修改6节点指针指向节点9.
算法步骤：
1、如果当前节点cur左子树是空的，那么访问此节点就可以，继续到右子树中去访问，
2、如果当前左子树不是空的，说明当前结点的前驱节点就在左子树中，就去左子树找。就可以在左子树中一直往右走，走到低就是当前节点的前驱。设置为pre。
如果pre的右子树是空的，修改pre的right指针即可，指向cur。
如果pre的右子树非空，说明已经被修改过。那么访问此节点即可，并把它的right改回来为null，然后继续在cur的右子树中找。
1 public static void MorrisInOrder(TreeNode root) { 2 TreeNode cur = root; 3 TreeNode pre; 4 while (cur != null) { 5 //左子树为空 6 if (cur.left == null) { 7 System.out.println(cur.val); 8 cur = cur.right; 9 continue;10 }11 //找它的前面节点12 pre = cur.left;13 while (pre.right != null && pre.right != cur) {14 pre = pre.right;15 }16 //找到后就要修改right指针17 if (pre.right == null) {18 pre.right = cur;19 //找下一个cur的前继20 cur = cur.left;21 } else { //之前就修改过了,继续找cur的后继22 pre.right = null;23 System.out.println(cur.val);24 cur = cur.right;25 }26 }27 }Morris中序遍历时间复杂度是O(n)，空间复杂度是O(1)。