Python二叉樹的層次遍歷怎么實現(xiàn)

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

題目

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

例如：

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

    3
   / \
  9  20
    /  \
   15   7

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

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

解題思路

思路：廣度優(yōu)先搜索（BFS）

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

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

• 從根節(jié)點開始搜索；

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

• 用棧存儲上述存儲每層節(jié)點值的列表，后續(xù)實現(xiàn)逆序。

具體代碼實現(xiàn)如下：

# 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二叉樹的層次遍歷怎么實現(xiàn)”的學習就結束了，希望能夠解決大家的疑惑。理論與實踐的搭配能更好的幫助大家學習，快去試試吧！若想繼續(xù)學習更多相關知識，請繼續(xù)關注億速云網(wǎng)站，小編會繼續(xù)努力為大家?guī)砀鄬嵱玫奈恼拢?/p>