# 二叉树的中序遍历 - Binary Tree Inorder Traversal

## 094. 二叉树的中序遍历 - Binary Tree Inorder Traversal

【中序遍历-递归】 【中序遍历-迭代】

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

### Example:

``````输入: [1,null,2,3]
1
\
2
/
3

``````

## Solutions

 ``````1 2 3 4 5 6 7 8 9 `````` ``````/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ ``````

### Solution 【中序遍历-递归】 ( 0ms)

 `````` 1 2 3 4 5 6 7 8 9 10 11 12 `````` ``````class Solution { List result = new LinkedList<>(); public List inorderTraversal(TreeNode root) { if (root != null){ //相比 if (root == null) return result; 会快1ms inorderTraversal(root.left); result.add(root.val); inorderTraversal(root.right); } return result; } } ``````

### Solution 【中序遍历-迭代】 ( 2ms)

 `````` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 `````` ``````class Solution { public List inorderTraversal(TreeNode root) { List result = new LinkedList<>(); Stack stack = new Stack(); TreeNode current = root; while (current != null || !stack.isEmpty()) { while (current != null) { stack.push(current); current = current.left; } if (!stack.isEmpty()) { current = stack.pop(); result.add(current.val); current = current.right; } } return result; } } ``````