代碼隨想錄算法訓練營第13天|二叉樹的遞歸遍歷、二叉樹的迭代遍歷、二叉樹的統一迭代法、102.二叉樹的層序遍歷

打卡Day13

  • 1.理論基礎
  • 2.二叉樹的遞歸遍歷
  • 3.二叉樹的迭代遍歷
  • 3.二叉樹的統一迭代法
  • 4.102.二叉樹的層序遍歷
    • 擴展
      • 107. 二叉樹的層序遍歷 II
      • 199.二叉樹的右視圖
      • 637.二叉樹的層平均值
      • 429.N叉樹的層序遍歷
      • 515.在每個樹行中找最大值
      • 116.填充每個節點的下一個右側節點指針
      • 117. 填充每個節點的下一個右側節點指針 II
      • 104. 二叉樹的最大深度
      • #111.二叉樹的最小深度

1.理論基礎

文檔講解： 代碼隨想錄

解題過程二叉樹有兩種主要形式：滿二叉樹和完全二叉樹。
（1）滿二叉樹：一棵二叉樹只有度為0的節點和度為2的節點，并且度為0的節點在同一層上。深度為 k 的滿二叉樹有 2^k - 1 個節點。

在這里插入圖片描述
（2）完全二叉樹：除了最底層節點可能沒填滿外，其余每層節點數都達到最大值，并且最下面的節點都集中在該層最左邊的若干位置。若最底層為第 h（h >= 1） 層，則該層包含 1 ~ 2^(h -1) 。

在這里插入圖片描述
之前優先級隊列其實是一個堆，堆是一顆完全二叉樹，同時保證父子節點的順序關系。

二叉搜索樹：是一個有序樹。
平衡二叉搜索樹：是一棵空樹或它的左右兩個子樹的高度差的絕對值不超過1，并且左右兩個子樹都是一棵平衡二叉樹。

二叉樹的定義：


class TreeNode:def __init__(self, val, left = None, right = None):self.val = valself.left = leftself.right = right

2.二叉樹的遞歸遍歷

文檔講解： 代碼隨想錄

遞歸算法的三要素：
（1）確定遞歸函數的參數和返回值：確定哪些參數是遞歸的過程中需要處理的，那么就在遞歸函數里加上這個參數，并且還要明確每次遞歸的返回值是什么進而確定遞歸函數的返回類型。
（2）確定終止條件：如果遞歸沒有終止，操作系統的內存站必然會溢出。運行遞歸算法遇到棧溢出的錯誤，就是沒寫終止條件或者終止條件寫的不對。
（3）確定單層遞歸的邏輯：確定每一層遞歸需要處理的信息，在這里也就會重復調用自己來實現遞歸的過程。

以前序遍歷為例：
（1）確定遞歸函數的參數和返回值：參數為當前樹節點，返回值為空。我本來以為需要返回節點的數據，但在函數的內部直接將數據加入到列表中。
（2）終止條件：當遍歷的節點為空，直接return。
（3）確定單層遞歸的邏輯：先取中節點的數值，再取左節點，最后右節點。

題目鏈接：前序遍歷

class Solution(object):def preorderTraversal(self, root):""":type root: TreeNode:rtype: List[int]"""res = []def dfs(node):if node is None:returnres.append(node.val)dfs(node.left)dfs(node.right)dfs(root)return res

題目鏈接：后序遍歷

class Solution(object):def postorderTraversal(self, root):""":type root: TreeNode:rtype: List[int]"""res = []def dfs(node):if node is None:returndfs(node.left)dfs(node.right)res.append(node.val)dfs(root)return res

題目鏈接：中序遍歷

class Solution(object):def inorderTraversal(self, root):""":type root: TreeNode:rtype: List[int]"""res = []def dfs(node):if node is None:return dfs(node.left)res.append(node.val)dfs(node.right)dfs(root)return res

3.二叉樹的迭代遍歷

文檔講解： 代碼隨想錄

題目鏈接：前序遍歷

class Solution(object):def preorderTraversal(self, root):""":type root: TreeNode:rtype: List[int]"""if not root:return []#跟節點先入棧stack = [root]res = []while stack:node = stack.pop()#處理中節點res.append(node.val)#右孩子先入棧if node.right:stack.append(node.right)#左孩子入棧if node.left:stack.append(node.left)return res

題目鏈接：后序遍歷

class Solution(object):def postorderTraversal(self, root):""":type root: TreeNode:rtype: List[int]"""if not root:return []stack = [root]res = []while stack:node = stack.pop()res.append(node.val)if node.left:stack.append(node.left)if node.right:stack.append(node.right)return res[::-1]

題目鏈接：中序遍歷

在中序遍歷中，處理元素和訪問元素的順序不一致，需要借助指針的遍歷來幫助訪問節點，棧用來處理節點上的元素。不能提前將根節點放入棧中，如果先放入的話，迭代處理會先訪問跟節點，而不是最左邊的葉子節點。

class Solution(object):def inorderTraversal(self, root):""":type root: TreeNode:rtype: List[int]"""if not root:return []res = []stack = []cur = rootwhile cur or stack:#先迭代訪問最左邊的葉子節點if cur:stack.append(cur)cur = cur.leftelse:#此時cur = nullcur = stack.pop()res.append(cur.val)cur = cur.rightreturn res

3.二叉樹的統一迭代法

文檔講解： 代碼隨想錄

題目鏈接：前序遍歷

class Solution(object):def preorderTraversal(self, root):""":type root: TreeNode:rtype: List[int]"""res = []stack = []if root:stack.append(root)while stack:node = stack.pop()if node != None:if node.right:stack.append(node.right)if node.left:stack.append(node.left)stack.append(node)stack.append(None)else:node = stack.pop()res.append(node.val)return res

題目鏈接：后序遍歷

class Solution(object):def postorderTraversal(self, root):""":type root: TreeNode:rtype: List[int]"""res = []stack = []if root:stack.append(root)while stack:node = stack.pop()if node != None:stack.append(node)stack.append(None)if node.left:stack.append(node.left)if node.right:stack.append(node.right)else:node = stack.pop()res.append(node.val)return res

題目鏈接：中序遍歷

class Solution(object):def inorderTraversal(self, root):""":type root: TreeNode:rtype: List[int]"""res = []stack = []if root:stack.append(root)while stack:node = stack.pop()if node != None:if node.right:stack.append(node.right)stack.append(node)stack.append(None)if node.left:stack.append(node.left)else:node = stack.pop()res.append(node.val)return res

4.102.二叉樹的層序遍歷

題目鏈接：102.二叉樹的層序遍歷
文檔講解： 代碼隨想錄

class Solution(object):def levelOrder(self, root):""":type root: TreeNode:rtype: List[List[int]]"""if not root:return []queue = collections.deque([root])res = []while queue:level = []for i in range(len(queue)):cur = queue.popleft()level.append(cur.val)if cur.left:queue.append(cur.left)if cur.right:queue.append(cur.right)res.append(level)return res

遞歸法：

class Solution(object):def levelOrder(self, root):""":type root: TreeNode:rtype: List[List[int]]"""if not root:return []levels = []def traverse(node, level):if not node:returnif len(levels) == level:levels.append([])levels[level].append(node.val)traverse(node.left, level + 1)traverse(node.right, level + 1)traverse(root, 0)return levels

擴展

107. 二叉樹的層序遍歷 II

題目鏈接：107

思路：在上題的基礎上，輸出的時候反轉一下順序。

class Solution(object):def levelOrderBottom(self, root):""":type root: TreeNode:rtype: List[List[int]]"""if not root:return []res = []queue = collections.deque([root])while queue:level = []for i in range(len(queue)):node = queue.popleft()level.append(node.val)if node.left:queue.append(node.left)if node.right:queue.append(node.right)res.append(level)return res[::-1]

199.二叉樹的右視圖

題目鏈接：199

一開始題目沒有理解好，以為是將每層元素從右往左組成列表輸出。題目要求的是只輸出每層最右邊元素組成的一維列表。

class Solution(object):def rightSideView(self, root):""":type root: TreeNode:rtype: List[int]"""if not root:return []res = []queue = collections.deque([root])while queue:#需要用變量存儲長度，因為下面會對隊列進行操作size = len(queue)for i in range(size):node = queue.popleft()if i == size - 1:res.append(node.val)if node.left:queue.append(node.left)if node.right:queue.append(node.right)return res

637.二叉樹的層平均值

題目鏈接：637

class Solution(object):def averageOfLevels(self, root):""":type root: TreeNode:rtype: List[float]"""if not root:return []queue = collections.deque([root])res = []while queue:summ = 0size = len(queue)for i in range(size):node = queue.popleft()summ += node.valif node.left:queue.append(node.left)if node.right:queue.append(node.right)res.append(round(summ / size, 4))return res

出現的問題：
在這里插入圖片描述

將自己的代碼替換到python3中是可行的，感覺是數據類型有點問題，具體是什么問題不能確認，暫時沒有解決。

429.N叉樹的層序遍歷

題目鏈接：429

class Solution(object):def levelOrder(self, root):""":type root: Node:rtype: List[List[int]]"""if not root:return []res = []queue = collections.deque([root])while queue:level = []size = len(queue)for i in range(size):node = queue.popleft()level.append(node.val)#用for循環遍歷孩子節點for child in node.children:queue.append(child)res.append(level)return res

515.在每個樹行中找最大值

題目鏈接：515

class Solution(object):def largestValues(self, root):""":type root: TreeNode:rtype: List[int]"""if not root:return []queue = collections.deque([root])res = []while queue:size = len(queue)maxx = queue[0].val#可以使用maxx = float('-inf')初始化for i in range(size):node = queue.popleft()if node.val > maxx:maxx = node.valif node.left:queue.append(node.left)if node.right:queue.append(node.right)res.append(maxx)return res

116.填充每個節點的下一個右側節點指針

題目鏈接：116

class Solution(object):def connect(self, root):""":type root: Node:rtype: Node"""if not root:return rootqueue = collections.deque([root])while queue:size = len(queue)pre = Nonefor i in range(size):node = queue.popleft()if pre:pre.next = nodepre = nodeif node.left:queue.append(node.left)if node.right:queue.append(node.right)return root

117. 填充每個節點的下一個右側節點指針 II

題目鏈接：117

class Solution(object):def connect(self, root):""":type root: Node:rtype: Node"""if not root:return rootqueue = collections.deque([root])while queue:size = len(queue)pre = None for i in range(size):node = queue.popleft()if pre:pre.next = nodepre = nodeif node.left:queue.append(node.left)if node.right:queue.append(node.right)return root

104. 二叉樹的最大深度

題目鏈接：104

class Solution(object):def maxDepth(self, root):""":type root: TreeNode:rtype: int"""if not root:return 0queue = collections.deque([root])deep = 0while queue:size = len(queue)deep += 1for i in range(size):node = queue.popleft()if node.left:queue.append(node.left)if node.right:queue.append(node.right)return deep

#111.二叉樹的最小深度

題目鏈接：111

class Solution(object):def minDepth(self, root):""":type root: TreeNode:rtype: int"""if not root:return 0deep = 0queue = collections.deque([root])while queue:size = len(queue)deep += 1for i in range(size):node = queue.popleft()if not node.left and not node.right:return deepif node.left:queue.append(node.left)if node.right:queue.append(node.right)return deep

本文來自互聯網用戶投稿，該文觀點僅代表作者本人，不代表本站立場。本站僅提供信息存儲空間服務，不擁有所有權，不承擔相關法律責任。
如若轉載，請注明出處：http://www.pswp.cn/web/40782.shtml
繁體地址，請注明出處：http://hk.pswp.cn/web/40782.shtml
英文地址，請注明出處：http://en.pswp.cn/web/40782.shtml

如若內容造成侵權/違法違規/事實不符，請聯系多彩編程網進行投訴反饋email:809451989@qq.com，一經查實，立即刪除！

相關文章

如何保證接口冪等性

如何保證接口冪等性

如何保證接口冪等性 1、冪等性是什么？ 接口冪等性是指用戶對于同一操作發起的一次請求或者多次請求的結果是一致的，不會因為多次點擊而產生了不同的結果。 2、使用冪等性的場景有哪些？ 頁面點擊保存按鈕時，不小心快速點了兩次…
閱讀更多...
Python面試題-6

Python面試題-6

1. 請解釋Python中的動態類型。 Python中的動態類型 Python是一種動態類型語言，這意味著你不需要在編程時聲明變量的類型，而是在運行時自動推斷類型。在Python中，變量的類型是在程序運行時決定的，這意味著同一個變量可以在不改變…
閱讀更多...
上萬組風電，光伏，用戶負荷數據分享

上萬組風電，光伏，用戶負荷數據分享

上萬組風電，光伏，用戶負荷數據分享 可用于風光負荷預測等研究 獲取鏈接🔗 https://pan.baidu.com/s/1izpymx6R3Y8JsFdx42rL0A 提取碼：381i 獲取鏈接🔗 https://pan.baidu.com/s/1izpymx6R3Y8JsFdx42rL0A 提取…
閱讀更多...
一行代碼用git新建分支

一行代碼用git新建分支

1.在本地創建分支 dev git branch dev2.切換分支 git checkout devwebstorm操作如下： 3.推送新分支到遠程 git push --set-upstream origin 分支名webstorm操作如下：提交代碼的時候會自動推送到遠程 4.到git上面可以看看剛剛推送的內容 dev多推送…
閱讀更多...
Proxmox VE 8虛擬機直通USB磁盤

Proxmox VE 8虛擬機直通USB磁盤

作者：田逸（fromyz） 今天有個兄弟發消息，咨詢怎么讓插在服務器上的U盾被Proxmox VE上的虛擬機識別。在很久很久以前，我嘗試過在Proxmox VE 5以前的版本創建windows虛擬機，并把插在Proxmox VE宿主機上的銀行U…
閱讀更多...
基于STM32設計的智能喂養系統(ESP8266+微信小程序)175

基于STM32設計的智能喂養系統(ESP8266+微信小程序)175

基于STM32設計的牛羊喂養系統(微信小程序)(175) 文章目錄 一、前言1.1 項目介紹【1】項目功能介紹【2】項目硬件模塊組成【3】ESP8266工作模式配置【4】上位機開發【5】項目模塊劃分1.2 項目功能需求1.3 項目開發背景1.4 開發工具的選擇1.5 系統框架圖1.6 系統原理圖1.7 硬件實…
閱讀更多...
Android ViewPostImeInputStage輸入事件處理

Android ViewPostImeInputStage輸入事件處理

InputDispatcher向InputChannel使用socket寫入輸入事件，觸發InputEventReceiver調用來接收輸入事件。 ViewPostImeInputStage處理view控件的事件 frameworks/base/core/java/android/view/InputEventReceiver.java dispatchInputEvent frameworks/base/core/jav…
閱讀更多...
SwinTransformer的相對位置索引的原理以及源碼分析

SwinTransformer的相對位置索引的原理以及源碼分析

文章目錄 1. 理論分析2. 完整代碼 引用：參考博客鏈接 1. 理論分析 根據論文中提供的公式可知是在 Q Q Q和 K K K進行匹配并除以 d \sqrt d d ? 后加上了相對位置偏執 B B B。 A t t e n t i o n ( Q , K , V ) S o f t m a x ( Q K T d B ) V \begin{aligned} &…
閱讀更多...
絕了，華為伸縮攝像頭如何突破影像邊界？

絕了，華為伸縮攝像頭如何突破影像邊界？

自華為Pura70 Ultra超聚光伸縮鏡頭誕生以來，備受大家的關注，聽說這顆鏡頭打破了傳統手機的攝像頭體積與鏡頭的設計，為我們帶來了不一樣的拍照體驗。 智能手機飛速發展的今天，影像功能已經成為我們衡量一款手機性能的重要指標。想…
閱讀更多...
MySQL中mycat與mha應用

MySQL中mycat與mha應用

目錄 一.Mycat代理服務器 1.Mycat應用場景 2.mycat安裝目錄結構說明 3.Mycat的常用配置文件 4.Mycat日志 5.mycat 實現讀寫分離 二.MySQL高可用 1.原理過程 2.MHA軟件 3.實現MHA 一.Mycat代理服務器 1.Mycat應用場景 Mycat適用的場景很豐富，以下是幾個典型…
閱讀更多...
進程輸入輸出及終端屬性學習

進程輸入輸出及終端屬性學習

進程的標準輸入輸出 當主進程fork或exec子進程，文件描述符被繼承，因此0,1,2句柄也被繼承，從而使得telnet等服務，可以做到間接調用別的shell或程序。比如如果是遠程登錄使用的zsh，那么其會重定向到相應的pts $ ps|gre…
閱讀更多...
滬上繁花：上海電信的5G-A之躍

滬上繁花：上海電信的5G-A之躍

2024年6月18日下午，在上海舉行的3GPP RAN第104次會議上，3GPP正式宣布R18標準凍結。R18是無線網絡面向5G-A的第一個版本，其成功凍結正式宣布了5G發展迎來新機遇，5G-A商用已進入全新的發展階段。 在5G-A滾滾而來的時代洪流中&#x…
閱讀更多...
C#實戰|賬號管理系統：通用登錄窗體的實現。

C#實戰|賬號管理系統：通用登錄窗體的實現。

哈嘍，你好啊，我是雷工！ 本節記錄登錄窗體的實現方法，比較有通用性，所有的項目登錄窗體實現基本都是這個實現思路。 一通百通，以下為學習筆記。 01 登錄窗體的邏輯 用戶在登錄窗輸入賬號和密碼，如果輸入賬號和密碼信息正確，點擊【登錄】按鈕，則跳轉顯示主窗體，同時在固…
閱讀更多...
Vue3項目初始化：

Vue3項目初始化：

緊接著前面的文章：https://blog.csdn.net/weixin_51416826/article/details/138679863?spm1001.2014.3001.5502 當我們生成一個Vue3項目后必須要增加一些依賴和配置，比如安裝組件庫、配置ESLint和Prettier、接下來咱一步步推進~ 安裝組件庫 一般開發…
閱讀更多...
【基礎篇】1.7 C語言基礎（一）

【基礎篇】1.7 C語言基礎（一）

一，為什么是C語言？ C語言是嵌入式系統開發領域廣泛使用的編程語言。STM32作為一種嵌入式系統的微控制器，需要精確控制硬件資源，那么C語言能夠滿足這一需求。 二，STM32 C語言常用基礎知識 下面是我們在日常STM32開發中必備的C語言基礎要點，掌握這些C語言的基礎知識要點…
閱讀更多...
llama3

llama3

Llama 3是由Meta公司發布的一款大型語言模型（LLM），該模型在發布后迅速引起了業界的廣泛關注。以下是對Llama 3的詳細介紹： 一、基本信息 發布單位：Meta公司 發布時間：當地時間2024年4月18日 主要特點&…
閱讀更多...
上海外貿建站公司wordpress模板推薦

上海外貿建站公司wordpress模板推薦

Sora索啦高端制造業wordpress主題 紅色高端制造業wordpress主題，適合外貿企業出海建獨立站的wordpress模板。 https://www.jianzhanpress.com/?p5885 Yamal外貿獨立站wordpress主題 綠色的亞馬爾Yamal外貿獨立站wordpress模板，適用于外貿公司建獨立站…
閱讀更多...
Redis 中 Set 和 Zset 類型

Redis 中 Set 和 Zset 類型

目錄 1.Set類型 1.1 Set集合 1.2 普通命令 1.3 集合操作 1.4 內部編碼 1.5 使用場景 2.Zset類型 2.1 Zset有序集合 2.2 普通命令 2.3 集合間操作 2.4 內部編碼 2.5 使用場景 1.Set類型 1.1 Set集合 集合類型也是保存多個字符串類型的元素，但是和列表類型不同的是&…
閱讀更多...
【Go】excelize庫實現excel導入導出封裝（四），導出時自定義某一列或多列的單元格樣式

【Go】excelize庫實現excel導入導出封裝（四），導出時自定義某一列或多列的單元格樣式

大家好，這里是符華~ 查看前三篇： 【Go】excelize庫實現excel導入導出封裝（一），自定義導出樣式、隔行背景色、自適應行高、動態導出指定列、動態更改表頭 【Go】excelize庫實現excel導入導出封裝（二&…
閱讀更多...
WY-35A4T三相電壓繼電器 導軌安裝 約瑟JOSEF

WY-35A4T三相電壓繼電器 導軌安裝 約瑟JOSEF

功能簡述 WY系列電壓繼電器是帶延時功能的數字式交流電壓繼電器。 可用于發電機，變壓器和輸電線的繼電保護裝置中，作為過電壓或欠電壓閉鎖的動作元件 LCD實時顯示當前輸入電壓值 額定輸入電壓Un:100VAC、200VAC、400VAC產品滿足電磁兼容四級標準 產品…
閱讀更多...
最新文章

Copyright @ 2022~2023