#94. 二叉树的中序遍历

给定一个二叉树，返回它的中序遍历。

示例:

1
2
3
4
5
6
7
8
输入: [1,null,2,3]
   1
    \
     2
    /
   3

输出: [1,3,2]

进阶:  递归算法很简单，你可以通过迭代算法完成吗？

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
package xyz.onns.leetcode;

import java.util.LinkedList;
import java.util.List;
import java.util.Stack;

/**
 * @Author Onns
 * @Date 2020/9/14 2:36 PM
 * @Version 1.0
 * @Website https://onns.xyz/blog/
 */
public class BinaryTreeInorderTraversal {
	public static void main(String[] args) {
		new BinaryTreeInorderTraversal().new Solution1().test();
		System.out.println();
		new BinaryTreeInorderTraversal().new Solution2().test();
		System.out.println();
		new BinaryTreeInorderTraversal().new Solution().test();
	}

	/**
	 * Definition for a binary tree node.
	 * public class TreeNode {
	 * int val;
	 * TreeNode left;
	 * TreeNode right;
	 * TreeNode(int x) { val = x; }
	 * }
	 */
	class TreeNode {
		int val;
		TreeNode left;
		TreeNode right;

		TreeNode(int x) {
			val = x;
		}
	}

	class Solution {
		public List<Integer> inorderTraversal(TreeNode root) {
			List<Integer> r = new LinkedList<>();
			TreeNode t = null;

			while (root != null) {
				if (root.left != null) {
					t = root.left;
					while (t.right != null && t.right != root) {
						t = t.right;
					}
					if (t.right == null) {
						t.right = root;
						root = root.left;
					} else {
						r.add(t.right.val);
						root = root.right;
						t.right = null;
					}


				} else {
					r.add(root.val);
					root = root.right;
				}

			}
			return r;
		}

		void test() {
			TreeNode root = new TreeNode(1);
			root.left = new TreeNode(2);
			root.left.left = new TreeNode(4);
			root.left.right = new TreeNode(5);
			root.right = new TreeNode(3);
			root.right.left = new TreeNode(6);
			root.right.right = new TreeNode(7);
			List<Integer> r = inorderTraversal(root);
			for (int i : r) {
				System.out.print(i + " "); // 4 2 5 1 6 3 7
			}
		}
	}

	class Solution2 {
		public List<Integer> inorderTraversal(TreeNode root) {
			List<Integer> r = new LinkedList<>();
			Stack<TreeNode> s = new Stack<>();
			while (root != null || !s.isEmpty()) {
				while (root != null) {
					s.push(root);
					root = root.left;
				}
				root = s.pop();
				r.add(root.val);
				root = root.right;
			}
			return r;
		}

		void test() {
			TreeNode root = new TreeNode(1);
			root.left = new TreeNode(2);
			root.left.left = new TreeNode(4);
			root.left.right = new TreeNode(5);
			root.right = new TreeNode(3);
			root.right.left = new TreeNode(6);
			root.right.right = new TreeNode(7);
			List<Integer> r = inorderTraversal(root);
			for (int i : r) {
				System.out.print(i + " "); // 4 2 5 1 6 3 7
			}
		}
	}

	class Solution1 {
		List<Integer> r;

		public List<Integer> inorderTraversal(TreeNode root) {
			r = new LinkedList<>();
			visit(root);
			return r;
		}

		void visit(TreeNode root) {
			if (root.left != null) {
				visit(root.left);
			}
			r.add(root.val);
			if (root.right != null) {
				visit(root.right);
			}
		}

		void test() {
			TreeNode root = new TreeNode(1);
			root.left = new TreeNode(2);
			root.left.left = new TreeNode(4);
			root.left.right = new TreeNode(5);
			root.right = new TreeNode(3);
			root.right.left = new TreeNode(6);
			root.right.right = new TreeNode(7);
			List<Integer> r = inorderTraversal(root);
			for (int i : r) {
				System.out.print(i + " "); // 4 2 5 1 6 3 7
			}
		}
	}
}

Morris 遍历算法是参照官方解做的：

https://leetcode-cn.com/problems/binary-tree-inorder-traversal/solution/er-cha-shu-de-zhong-xu-bian-li-by-leetcode-solutio/

Morris 遍历算法是另一种遍历二叉树的方法，它能将非递归的中序遍历空间复杂度降为 O(1)。

Morris 遍历算法整体步骤如下（假设当前遍历到的节点为 x）：

  1. 如果 x 无左孩子，先将 x 的值加入答案数组，再访问 x 的右孩子，即 $x=x.\textit{right}$ 。
  2. 如果 x 有左孩子，则找到 x 左子树上最右的节点（即左子树中序遍历的最后一个节点，x 在中序遍历中的前驱节点），我们记为 $\textit{predecessor}$ 。根据 $\textit{predecessor}$ 的右孩子是否为空，进行如下操作。
    • 如果 $\textit{predecessor}$ 的右孩子为空，则将其右孩子指向 x，然后访问 x 的左孩子，即 $x=x.\textit{left}$ 。
    • 如果 $\textit{predecessor}$ 的右孩子不为空，则此时其右孩子指向 x，说明我们已经遍历完 x 的左子树，我们将 $\textit{predecessor}$ 的右孩子置空，将 x 的值加入答案数组，然后访问 x 的右孩子，即 $x=x.\textit{right}$ 。
  3. 重复上述操作，直至访问完整棵树。