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

創(chuàng)新互聯(lián)公司是一家專(zhuān)注于網(wǎng)站制作、網(wǎng)站建設(shè)與策劃設(shè)計(jì),長(zhǎng)安網(wǎng)站建設(shè)哪家好?創(chuàng)新互聯(lián)公司做網(wǎng)站,專(zhuān)注于網(wǎng)站建設(shè)10年,網(wǎng)設(shè)計(jì)領(lǐng)域的專(zhuān)業(yè)建站公司;建站業(yè)務(wù)涵蓋:長(zhǎng)安等地區(qū)。長(zhǎng)安做網(wǎng)站價(jià)格咨詢(xún):18982081108

題目

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

例如：

給定二叉樹(shù) [3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7

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

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

解題思路

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

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

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

• 從根節(jié)點(diǎn)開(kāi)始搜索；

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

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

具體代碼實(shí)現(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

到此，關(guān)于“Python二叉樹(shù)的層次遍歷怎么實(shí)現(xiàn)”的學(xué)習(xí)就結(jié)束了，希望能夠解決大家的疑惑。理論與實(shí)踐的搭配能更好的幫助大家學(xué)習(xí)，快去試試吧！若想繼續(xù)學(xué)習(xí)更多相關(guān)知識(shí)，請(qǐng)繼續(xù)關(guān)注創(chuàng)新互聯(lián)網(wǎng)站，小編會(huì)繼續(xù)努力為大家?guī)?lái)更多實(shí)用的文章！