【题目】

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

示例:

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

输出: [1,3,2]

进阶: 递归算法很简单，你可以通过迭代算法完成吗？

【思路】

前序遍历、中序遍历、后序遍历，这三种遍历方式中，前中后指的都是根节点的顺序，并且都是先遍历左子树、再遍历右子树。

中序遍历递归解法：先递归遍历左子树，再访问当前节点的值，最后递归遍历右子树。

中序遍历非递归解法：使用两个栈，一个栈（栈1）存储节点，另一个栈（栈2）存储访问标签。要想实现左根右的顺序，则需要先插入右节点，再插入根节点，最后插入左节点，实现步骤为：如果栈1的栈顶节点没被访问，则弹出该节点，并将右孩子节点（若有）加入栈中，将该节点加入栈，最后将左孩子节点（若有）加入栈中；同时栈2加入对应的是否被访问的标签。

【代码】

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 traverse(self, node):
        if not node:
            return
        
        # 左根右
        self.traverse(node.left)
        self.res.append(node.val)
        self.traverse(node.right)
    
    def inorderTraversal(self, root: TreeNode) -> List[int]:
        self.res = []
        self.traverse(root)
        return self.res

非递归解法

class Solution:    
    def inorderTraversal(self, root: TreeNode) -> List[int]:
        '''非递归遍历'''
        if not root:
            return []
        stack = [root]
        visit = [0]
        res = []
        while len(stack) > 0:
            # 已经遍历过，将val放到res中
            if visit[-1] == 1:
                res.append(stack.pop().val)
                visit.pop()
            # 未遍历过，则遍历左右节点（由于是栈，先保存右节点，再保存左节点）    
            else:
                node = stack.pop()
                visit_i = visit.pop()
                if node.right:
                    stack.append(node.right)
                    visit.append(0)
                stack.append(node)
                visit.append(1)
                if node.left:
                    stack.append(node.left)
                    visit.append(0)
                
        return res