给定一个二叉树，返回它的中序 遍历。
示例:
输入: [1,null,2,3]
1
\
2
/
3
输出: [1,3,2]
进阶: 递归算法很简单，你可以通过迭代算法完成吗？
解题思路
这是一个基础问题，和这个问题类似Leetcode 144:二叉树的前序遍历（最详细解决方案！！！）
class Solution:
def __init__(self):
self.ret = []
def inorderTraversal(self, root):
"""
:type root: TreeNode
:rtype: List[int]
"""
if root != None:
self.inorderTraversal(root.left)
self.ret.append(root.val)
self.inorderTraversal(root.right)
return self.ret
如果我们使用给递归的方法要怎么做呢？我们实际上可以模拟栈的操作。对于这个问题，实际上在计算机中是这样处理的。我们首先将访问node1的right、打印和访问node1的left压入栈中。
stack : go-1-R cout go-1-L
然后弹出访问node1的left，我们发现它是空，所以什么都不操作。接着打印。接着访问，我们这个时候要推入新的指令go-2-R、cout和go-2-L。
stack : go-2-R cout go-2-L
然后弹出go-2-L，接着我们要推入新的指令go-3-R、cout和go-3-L。
stack : go-2-R go-3-R cout go-3-L
接着就是弹出这些指令就可以了。假如我们通过对之前Leetcode 144:二叉树的前序遍历（最详细解决方案！！！） 做一些修改，得到如下操作：
class Solution:
def preorderTraversal(self, root):
"""
:type root: TreeNode
:rtype: List[int]
"""
result = list()
if root == None:
return result
stack = list()
stack.append(root)
while len(stack) != 0:
top = stack.pop()
if top.right != None:
stack.append(top.right)
result.append(top.val)
if top.left != None:
stack.append(top.left)
return result
实际上这个代码是不行的，这里的()不能理解为放在了中间就可以了。以下伪代码写法才是符合栈的本意：
while len(stack) != 0:
top = stack.pop()
if top == cout操作:
result.append(top.val)
continue
if top.right != None:
stack.append(top.right)
stack.append(cout操作)
if top.left != None:
stack.append(top.left)
但是我们想要表述这种cout操作，我们就不得不使用一些较复杂的数据结构，这是我们不希望看到的。我们有没有更好的做法呢？
其实我们再回想一下上面的栈操作，其实不难发现是这样的：
- 如果
root不为空，我们一直压入root，并且更新root=，这样left会一直压栈操作。 - 当我们发现
left为空的时候，我们就要将结果压入result，接着访问right，然后回到第一步 - 直到
len(stack)==0，我们就结束了。
我们根据上述思路，可以很容易地写出下面的代码：
class Solution:
def inorderTraversal(self, root):
"""
:type root: TreeNode
:rtype: List[int]
"""
result = list()
if root == None:
return result
stack = list()
while stack or root:
if root != None:
stack.append(root)
root = root.left
else:
root = stack.pop()
result.append(root.val)
root = root.right
return result
我将该问题的其他语言版本添加到了我的GitHub Leetcode
如有问题，希望大家指出！！！