# [94. 二叉树的中序遍历](https://leetcode-cn.com/problems/binary-tree-inorder-traversal)
[English Version](/solution/0000-0099/0094.Binary%20Tree%20Inorder%20Traversal/README_EN.md)
## 题目描述
<!-- 这里写题目描述 -->
<p>给定一个二叉树的根节点 <code>root</code> ，返回它的 <strong>中序</strong> 遍历。</p>
<p> </p>
<p><strong>示例 1：</strong></p>
<img alt="" src="https://cdn.jsdelivr.net/gh/doocs/leetcode@main/solution/0000-0099/0094.Binary%20Tree%20Inorder%20Traversal/images/inorder_1.jpg" style="width: 202px; height: 324px;" />
<pre>
<strong>输入：</strong>root = [1,null,2,3]
<strong>输出：</strong>[1,3,2]
</pre>
<p><strong>示例 2：</strong></p>
<pre>
<strong>输入：</strong>root = []
<strong>输出：</strong>[]
</pre>
<p><strong>示例 3：</strong></p>
<pre>
<strong>输入：</strong>root = [1]
<strong>输出：</strong>[1]
</pre>
<p><strong>示例 4：</strong></p>
<img alt="" src="https://cdn.jsdelivr.net/gh/doocs/leetcode@main/solution/0000-0099/0094.Binary%20Tree%20Inorder%20Traversal/images/inorder_5.jpg" style="width: 202px; height: 202px;" />
<pre>
<strong>输入：</strong>root = [1,2]
<strong>输出：</strong>[2,1]
</pre>
<p><strong>示例 5：</strong></p>
<img alt="" src="https://cdn.jsdelivr.net/gh/doocs/leetcode@main/solution/0000-0099/0094.Binary%20Tree%20Inorder%20Traversal/images/inorder_4.jpg" style="width: 202px; height: 202px;" />
<pre>
<strong>输入：</strong>root = [1,null,2]
<strong>输出：</strong>[1,2]
</pre>
<p> </p>
<p><strong>提示：</strong></p>
<ul>
<li>树中节点数目在范围 <code>[0, 100]</code> 内</li>
<li><code>-100 <= Node.val <= 100</code></li>
</ul>
<p> </p>
<p><strong>进阶:</strong> 递归算法很简单，你可以通过迭代算法完成吗？</p>
## 解法
<!-- 这里可写通用的实现逻辑 -->
**1. 递归遍历**
先递归左子树，再访问根节点，接着递归右子树。
**2. 栈实现非递归遍历**
非递归的思路如下：
1. 定义一个栈 stk
2. 将树的左节点依次入栈
3. 左节点为空时，弹出栈顶元素并处理
4. 重复 2-3 的操作
**3. Morris 实现中序遍历**
Morris 遍历无需使用栈，空间复杂度为 O(1)。核心思想是：
遍历二叉树节点，
1. 若当前节点 root 的左子树为空，**将当前节点值添加至结果列表 ans** 中，并将当前节点更新为 `root.right`
2. 若当前节点 root 的左子树不为空，找到左子树的最右节点 prev（也即是 root 节点在中序遍历下的前驱节点）：
- 若前驱节点 prev 的右子树为空，将前驱节点的右子树指向当前节点 root，并将当前节点更新为 `root.left`。
- 若前驱节点 prev 的右子树不为空，**将当前节点值添加至结果列表 ans** 中，然后将前驱节点右子树指向空（即解除 prev 与 root 的指向关系），并将当前节点更新为 `root.right`。
3. 循环以上步骤，直至二叉树节点为空，遍历结束。
<!-- tabs:start -->
### **Python3**
<!-- 这里可写当前语言的特殊实现逻辑 -->
递归：
```python
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
def dfs(root):
if root is None:
return
dfs(root.left)
nonlocal ans
ans.append(root.val)
dfs(root.right)
ans = []
dfs(root)
return ans
```
栈实现非递归：
```python
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
ans, stk = [], []
while root or stk:
if root:
stk.append(root)
root = root.left
else:
root = stk.pop()
ans.append(root.val)
root = root.right
return ans
```
Morris 遍历:
```python
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
ans = []
while root:
if root.left is None:
ans.append(root.val)
root = root.right
else:
prev = root.left
while prev.right and prev.right != root:
prev = prev.right
if prev.right is None:
prev.right = root
root = root.left
else:
ans.append(root.val)
prev.right = None
root = root.right
return ans
```
### **Java**
<!-- 这里可写当前语言的特殊实现逻辑 -->
递归：
```java
/**
* Definition for a binary tree node.
* 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;
* }
* }
*/
class Solution {
private List<Integer> ans;
public List<Integer> inorderTraversal(TreeNode root) {
ans = new ArrayList<>();
dfs(root);
return ans;
}
private void dfs(TreeNode root) {
if (root == null) {
return;
}
dfs(root.left);
ans.add(root.val);
dfs(root.right);
}
}
```
栈实现非递归：
```java
/**
* Definition for a binary tree node.
* 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;
* }
* }
*/
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> ans = new ArrayList<>();
Deque<TreeNode> stk = new ArrayDeque<>();
while (root != null || !stk.isEmpty()) {
if (root != null) {
stk.push(root);
root = root.left;
} else {
root = stk.pop();
ans.add(root.val);
root = root.right;
}
}
return ans;
}
}
```
Morris 遍历:
```java
/**
* Definition for a binary tree node.
* 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;
* }
* }
*/
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> ans = new ArrayList<>();
while (root != null) {
if (root.left == null) {
ans.add(root.val);
root = root.right;
} else {
TreeNode prev = root.left;
while (prev.right != null && prev.right != root) {
prev = prev.right;
}
if (prev.right == null) {
prev.right = root;
root = root.left;
} else {
ans.add(root.val);
prev.right = null;
root = root.right;
}
}
}
return ans;
}
}
```
### **JavaScript**
递归：
```js
/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {TreeNode} root
* @return {number[]}
*/
var inorderTraversal = function (root) {
let ans = [];
function dfs(root) {
if (!root) return;
dfs(root.left);
ans.push(root.val);
dfs(root.right);
}
dfs(root);
return ans;
};
```
栈实现非递归：
```js
/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {TreeNode} root
* @return {number[]}
*/
var inorderTraversal = function (root) {
let ans = [],
stk = [];
while (root || stk.length > 0) {
if (root) {
stk.push(root);
root = root.left;
} else {
root = stk.pop();
ans.push(root.val);
root = root.right;
}
}
return ans;
};
```
Morris 遍历:
```js
/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {TreeNode} root
* @return {number[]}
*/
var inorderTraversal = function (root) {
let ans = [];
while (root) {
if (!root.left) {
ans.push(root.val);
root = root.right;
} else {
let prev = root.left;
while (prev.right && prev.right != root) {
prev = prev.right;
}
if (!prev.right) {
prev.right = root;
root = root.left;
} else {
ans.push(root.val);
prev.right = null;
root = root.right;
}
}
}
return ans;
};
```
### **C++**
```cpp
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
vector<int> inorderTraversal(TreeNode* root) {
vector<int> ans;
while (root)
{
if (!root->left)
{
ans.push_back(root->val);
root = root->right;
}
else
{
TreeNode* prev = root->left;
while (prev->right && prev->right != root)
{
prev = prev->right;
}
if (!prev->right)
{
prev->right = root;
root = root->left;
}
else
{
ans.push_back(root->val);
prev->right = nullptr;
root = root->right;
}
}
}
return ans;
}
};
```
### **Go**
```go
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func inorderTraversal(root *TreeNode) []int {
var ans []int
for root != nil {
if root.Left == nil {
ans = append(ans, root.Val)
root = root.Right
} else {
prev := root.Left
for prev.Right != nil && prev.Right != root {
prev = prev.Right
}
if prev.Right == nil {
prev.Right = root
root = root.Left
} else {
ans = append(ans, root.Val)
prev.Right = nil
root = root.Right
}
}
}
return ans
}
```
### **...**
```
```
<!-- tabs:end -->