中序遍历的两种实现方式（都是基于迭代）

[zshuangyan]

方式一

def travelNode(node):
    if not node:
        return []

    stack = [node]
    tmp = []
    result = []
    while stack:
        node = stack.pop()
        while node:
            tmp.append(node)
            node = node.left

        while tmp:
            node = tmp.pop()
            result.append(node.val)
            if node.right:
                stack.append(node.right)
                break

    return result

方式二

def inorderTraversal(root):
    """ 
    :type root: TreeNode
    :rtype: List[int]
    """ 
    if root == None:
        return []

    stack = [root]
    queue = []

    while stack:
        node = stack.pop()
        if isinstance(node, int):
            queue.append(node)
        else:
            if node.right:
                stack.append(node.right)
            stack.append(node.val)
            if node.left:
                stack.append(node.left)

    return queue