怎樣返回的python中序遍歷

【題目】

給定一個(gè)二叉樹(shù)，返回它的中序 遍歷。

示例:

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

輸出: [1,3,2]

進(jìn)階: 遞歸算法很簡(jiǎn)單，你可以通過(guò)迭代算法完成嗎？

【思路】

前序遍歷、中序遍歷、后序遍歷，這三種遍歷方式中，前中后指的都是根節(jié)點(diǎn)的順序，并且都是先遍歷左子樹(shù)、再遍歷右子樹(shù)。

中序遍歷遞歸解法：先遞歸遍歷左子樹(shù)，再訪問(wèn)當(dāng)前節(jié)點(diǎn)的值，最后遞歸遍歷右子樹(shù)。

中序遍歷非遞歸解法：使用兩個(gè)棧，一個(gè)棧（棧1）存儲(chǔ)節(jié)點(diǎn)，另一個(gè)棧（棧2）存儲(chǔ)訪問(wèn)標(biāo)簽。要想實(shí)現(xiàn)左根右的順序，則需要先插入右節(jié)點(diǎn)，再插入根節(jié)點(diǎn)，最后插入左節(jié)點(diǎn)，實(shí)現(xiàn)步驟為：如果棧1的棧頂節(jié)點(diǎn)沒(méi)被訪問(wèn)，則彈出該節(jié)點(diǎn)，并將右孩子節(jié)點(diǎn)（若有）加入棧中，將該節(jié)點(diǎn)加入棧，最后將左孩子節(jié)點(diǎn)（若有）加入棧中；同時(shí)棧2加入對(duì)應(yīng)的是否被訪問(wèn)的標(biāo)簽。

【代碼】

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:
            # 已經(jīng)遍歷過(guò)，將val放到res中
            if visit[-1] == 1:
                res.append(stack.pop().val)
                visit.pop()
            # 未遍歷過(guò)，則遍歷左右節(jié)點(diǎn)（由于是棧，先保存右節(jié)點(diǎn)，再保存左節(jié)點(diǎn)）    
            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