【題目】

給定一個二叉樹，返回它的中序 遍歷。

示例:

輸入: [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