亚洲激情专区-91九色丨porny丨老师-久久久久久久女国产乱让韩-国产精品午夜小视频观看

溫馨提示×

溫馨提示×

您好,登錄后才能下訂單哦!

密碼登錄×
登錄注冊×
其他方式登錄
點擊 登錄注冊 即表示同意《億速云用戶服務條款》

怎樣返回的python中序遍歷

發布時間:2021-12-13 16:47:21 來源:億速云 閱讀:149 作者:柒染 欄目:大數據

這期內容當中小編將會給大家帶來有關怎樣返回的python中序遍歷,文章內容豐富且以專業的角度為大家分析和敘述,閱讀完這篇文章希望大家可以有所收獲。

【題目】

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

示例:

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

上述就是小編為大家分享的怎樣返回的python中序遍歷了,如果剛好有類似的疑惑,不妨參照上述分析進行理解。如果想知道更多相關知識,歡迎關注億速云行業資訊頻道。

向AI問一下細節

免責聲明:本站發布的內容(圖片、視頻和文字)以原創、轉載和分享為主,文章觀點不代表本網站立場,如果涉及侵權請聯系站長郵箱:is@yisu.com進行舉報,并提供相關證據,一經查實,將立刻刪除涉嫌侵權內容。

AI

太和县| 鞍山市| 康平县| 普安县| 新竹市| 基隆市| 莆田市| 玉龙| 乌兰县| 宿迁市| 玉屏| 兴山县| 木里| 泰来县| 拉萨市| 灯塔市| 临武县| 达尔| 天津市| 登封市| 潢川县| 攀枝花市| 岐山县| 板桥市| 广西| 堆龙德庆县| 阜平县| 吐鲁番市| 大荔县| 双柏县| 崇信县| 武穴市| 嘉祥县| 奈曼旗| 怀柔区| 陆良县| 泉州市| 隆子县| 福鼎市| 兴海县| 界首市|