给定一个二叉树，返回它的中序遍历。
示例:
输入: [1,null,2,3]
1
\
2
/
3
输出: [1,3,2]
进阶: 递归算法很简单，你可以通过迭代算法完成吗？
中序遍历首先遍历左子树，然后访问根结点，最后遍历右子树。
顺序：左 — 根 — 右
若二叉树为空则结束返回，否则：
（1）中序遍历左子树
（2）访问根结点
（3）中序遍历右子树
如下图所示二叉树
中序遍历结果：DBEAFC
解法一：
递归求解，难度不大，重点是确定好什么时候将结点添加进 List。
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<>();
inorder(root, list);
return list;
}
public void inorder(TreeNode root, List<Integer> list) {
if (root == null)
return;
inorder(root.left, list);
list.add(root.val);
inorder(root.right, list);
}
解法二：
迭代求解，这里我采用的是 ArrayDeque，基于数组的双端队列。当然，你也可以使用 Deque 或者 Stack。思路就是先把当前节点以及它的左节点存入队列或栈中，然后取出最后一次存入的节点，将它的值存入 List，更换当前节点为取出节点的右节点，重复上述操作。
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<>();
ArrayDeque<TreeNode> arrayDeque = new ArrayDeque<>();
while (root != null || !arrayDeque.isEmpty()) {
while (root != null) {
arrayDeque.addFirst(root);
root = root.left;
}
TreeNode treeNode = arrayDeque.removeFirst();
list.add(treeNode.val);
root = treeNode.right;
}
return list;
}
