Python二叉樹的層次遍歷怎么實現

這篇文章主要介紹“Python二叉樹的層次遍歷怎么實現”，在日常操作中，相信很多人在Python二叉樹的層次遍歷怎么實現問題上存在疑惑，小編查閱了各式資料，整理出簡單好用的操作方法，希望對大家解答”Python二叉樹的層次遍歷怎么實現”的疑惑有所幫助！接下來，請跟著小編一起來學習吧！

題目

給定一個二叉樹，返回其節點值自底向上的層次遍歷。 （即按從葉子節點所在層到根節點所在的層，逐層從左向右遍歷）

例如：

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

    3
   / \
  9  20
    /  \
   15   7

返回其自底向上的層次遍歷為：

[
  [15,7],
  [9,20],
  [3]
]

解題思路

思路：廣度優先搜索（BFS）

先看題目，題目要求返回節點值自底向上的層次遍歷。（從葉子節點所在層往根節點所在層，逐層從左到右遍歷）。

那么我們可以發現，使用廣度優先搜索的方法是最直觀的，題目要求自底向上，這里我從上到下遍歷搜索時先用棧存儲，然后再實現逆序（即自底向上）。具體的做法如下：

• 從根節點開始搜索；

• 每次搜索的時候先確定當前層的節點數量，遍歷當前層的全部節點，用列表存儲當前層的節點值；

• 用棧存儲上述存儲每層節點值的列表，后續實現逆序。

具體代碼實現如下：

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

from collections import deque

class Solution:
    def levelOrderBottom(self, root: TreeNode) -> List[List[int]]:
        if not root:
            return []
        
        ans = []

        stack = []

        queue = deque()
        queue.append(root)

        while queue:
            cnt = len(queue)
            
            tmp = []

            for _ in range(cnt):
                node = queue.popleft()
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
                tmp.append(node.val)
            
            stack.append(tmp)
        
        while stack:
            ans.append(stack.pop())
        
        return ans

到此，關于“Python二叉樹的層次遍歷怎么實現”的學習就結束了，希望能夠解決大家的疑惑。理論與實踐的搭配能更好的幫助大家學習，快去試試吧！若想繼續學習更多相關知識，請繼續關注億速云網站，小編會繼續努力為大家帶來更多實用的文章！