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

溫馨提示×

溫馨提示×

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

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

怎樣進行從上到下打印python二叉樹的分析

發布時間:2021-12-13 17:29:37 來源:億速云 閱讀:187 作者:柒染 欄目:大數據

本篇文章為大家展示了怎樣進行從上到下打印python二叉樹的分析,內容簡明扼要并且容易理解,絕對能使你眼前一亮,通過這篇文章的詳細介紹希望你能有所收獲。

題目描述

從上到下按層打印二叉樹,同一層的節點按從左到右的順序打印,每一層打印到一行。

  • 節點總數 <= 1000
     

題目樣例

示例

     
輸入

給定二叉樹: [3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7
           
輸出
[
  [3],
  [9,20],
  [15,7]
]
           

題目思考

  1. 如何記錄當前層的信息?
     

解決方案

     

思路

  • 相比昨天那道題, 這里需要把每層節點都單獨打印出來, 如果仍使用昨天的方法, 就無法知道每層的邊界在哪, 所以需要做出一些改變
  • 如果我們能夠記錄下當前層的節點邊界, 然后當前層的子節點都加入隊列后, 將隊列更新為從下一層節點起點開始, 這樣就確保每一層都單獨被記下來了
  • 這就是今天這道題的思路: 按照每層來循環, 存當前層的節點長度 curlen, 新追加的下層節點起點下標自然就是 curlen, 所以當前層遍歷完之后只需要將隊列切片成 curlen 及以后的部分即可
  • 同樣的, 由于是樹, 每個節點只需要遍歷一次, 所以不需要 visit 集合
  • 下面的代碼又是個人覺得比較通用的另一個 BFS 模板, 它適用于需要單獨處理每一層節點的情況, 供大家參考
     
復雜度
  • 時間復雜度         O(N)
    • 每個節點只需要遍歷一次
  • 空間復雜度         O(N)
    • 額外需要一個隊列
     
代碼
class Solution:
    def levelOrder(self, root: TreeNode) -> List[List[int]]:
        res = []
        if not root:
            return res
        q = [root]
        while q:
            # 當前層長度
            curlen = len(q)
            curlevel = []
            for node in q[:curlen]:
                # 將當前層的節點值依次加入結果中
                curlevel.append(node.val)
                # 只追加非空子節點
                if node.left:
                    q.append(node.left)
                if node.right:
                    q.append(node.right)
            res.append(curlevel)
            # 隊列切片, 開始處理下一層
            q = q[curlen:]
        return res

上述內容就是怎樣進行從上到下打印python二叉樹的分析,你們學到知識或技能了嗎?如果還想學到更多技能或者豐富自己的知識儲備,歡迎關注億速云行業資訊頻道。

向AI問一下細節

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

AI

乐清市| 祥云县| 宜兴市| 祁阳县| 始兴县| 龙南县| 交口县| 班玛县| 武宣县| 高邮市| 凤翔县| 多伦县| 紫阳县| 新野县| 天柱县| 如东县| 祁东县| 波密县| 凉城县| 含山县| 江油市| 永胜县| 廊坊市| 镶黄旗| 务川| 库尔勒市| 额敏县| 扎鲁特旗| 静安区| 鞍山市| 阳泉市| 任丘市| 紫阳县| 新野县| 辛集市| 洱源县| 德庆县| 怀仁县| 青川县| 三都| 万安县|