網(wǎng)站建設(shè)的基本流程包括網(wǎng)絡(luò)營銷ppt怎么做
Python藍(lán)橋杯訓(xùn)練:基本數(shù)據(jù)結(jié)構(gòu) [二叉樹] 中
文章目錄
- Python藍(lán)橋杯訓(xùn)練:基本數(shù)據(jù)結(jié)構(gòu) [二叉樹] 中
- 一、[翻轉(zhuǎn)二叉樹](https://leetcode.cn/problems/invert-binary-tree/)
- 二、[對(duì)稱二叉樹](https://leetcode.cn/problems/symmetric-tree/)
- 三、[二叉樹的最大深度](https://leetcode.cn/problems/maximum-depth-of-binary-tree/)
- 四、[二叉樹的最小深度](https://leetcode.cn/problems/minimum-depth-of-binary-tree/)
- 五、[完全二叉樹的節(jié)點(diǎn)個(gè)數(shù)](https://leetcode.cn/problems/count-complete-tree-nodes/)
- 六、[平衡二叉樹](https://leetcode.cn/problems/balanced-binary-tree/)
一、翻轉(zhuǎn)二叉樹
給你一棵二叉樹的根節(jié)點(diǎn) root
,翻轉(zhuǎn)這棵二叉樹,并返回其根節(jié)點(diǎn)。
示例 1:
輸入:root = [4,2,7,1,3,6,9]
輸出:[4,7,2,9,6,3,1]
示例 2:
輸入:root = [2,1,3]
輸出:[2,3,1]
示例 3:
輸入:root = []
輸出:[]
提示:
- 樹中節(jié)點(diǎn)數(shù)目范圍在
[0, 100]
內(nèi) -100 <= Node.val <= 100
這道題目要求我們翻轉(zhuǎn)一棵二叉樹,可以使用遞歸的思路來解決問題。對(duì)于一個(gè)二叉樹而言,可以將它的左右子樹看作兩個(gè)獨(dú)立的小問題,因此可以先將左右子樹分別翻轉(zhuǎn),然后再將整個(gè)樹進(jìn)行翻轉(zhuǎn)。
具體實(shí)現(xiàn)時(shí),可以編寫一個(gè)遞歸函數(shù),對(duì)于每一個(gè)節(jié)點(diǎn)而言,先分別翻轉(zhuǎn)左右子樹,然后將左右子樹交換即可。如果節(jié)點(diǎn)為空,直接返回即可。
class Solution:def invertTree(self, root: TreeNode) -> TreeNode:if not root:return None# 遞歸翻轉(zhuǎn)左右子樹left = self.invertTree(root.left)right = self.invertTree(root.right)# 交換左右子樹root.left = rightroot.right = leftreturn root
上面算法我們使用的遍歷順序是后序遍歷,使用前序遍歷也可以解決,該算法的時(shí)間復(fù)雜度為 O(n)O(n)O(n),其中 nnn 是二叉樹的節(jié)點(diǎn)個(gè)數(shù),因?yàn)槊總€(gè)節(jié)點(diǎn)都會(huì)被訪問一次。空間復(fù)雜度為 O(n)O(n)O(n),因?yàn)檫f歸函數(shù)會(huì)使用系統(tǒng)棧,最壞情況下系統(tǒng)棧的深度等于二叉樹的高度,即為 O(n)O(n)O(n)。
二、對(duì)稱二叉樹
給你一個(gè)二叉樹的根節(jié)點(diǎn) root
, 檢查它是否軸對(duì)稱。
示例 1:
輸入:root = [1,2,2,3,4,4,3]
輸出:true
示例 2:
輸入:root = [1,2,2,null,3,null,3]
輸出:false
提示:
- 樹中節(jié)點(diǎn)數(shù)目在范圍
[1, 1000]
內(nèi) -100 <= Node.val <= 100
**進(jìn)階:**你可以運(yùn)用遞歸和迭代兩種方法解決這個(gè)問題嗎?
首先,可以通過遞歸的方法來判斷一棵二叉樹是否是鏡像對(duì)稱的。對(duì)于一棵二叉樹而言,如果它是鏡像對(duì)稱的,那么它的左右子樹也是鏡像對(duì)稱的。因此,可以編寫一個(gè)遞歸函數(shù)來判斷左右子樹是否鏡像對(duì)稱,然后判斷根節(jié)點(diǎn)的左右子樹是否鏡像對(duì)稱即可。
具體實(shí)現(xiàn)時(shí),可以編寫一個(gè)遞歸函數(shù) isMirror
,該函數(shù)接受兩個(gè)參數(shù) left
和 right
,分別表示兩棵子樹。如果兩棵子樹均為空,返回 True
;如果其中一棵子樹為空,返回 False
;如果兩棵子樹的根節(jié)點(diǎn)的值不相等,返回 False
;否則,遞歸判斷兩棵子樹的左右子樹是否鏡像對(duì)稱。
class Solution(object):def isSymmetric(self, root):# 如果二叉樹為空,則直接返回 Trueif not root:return True# 如果二叉樹不為空,則遞歸判斷其左右子樹是否鏡像對(duì)稱return self.isMirror(root.left, root.right)def isMirror(self, left, right):# 如果兩棵二叉樹均為空,則返回 Trueif not left and not right:return True# 如果其中一棵二叉樹為空,則返回 Falseif not left or not right:return False# 如果兩棵二叉樹的根節(jié)點(diǎn)的值不相等,則返回 Falseif left.val != right.val:return False# 遞歸判斷兩棵二叉樹的左右子樹是否鏡像對(duì)稱return self.isMirror(left.left, right.right) and self.isMirror(left.right, right.left)
三、二叉樹的最大深度
給定一個(gè)二叉樹,找出其最大深度。
二叉樹的深度為根節(jié)點(diǎn)到最遠(yuǎn)葉子節(jié)點(diǎn)的最長路徑上的節(jié)點(diǎn)數(shù)。
說明: 葉子節(jié)點(diǎn)是指沒有子節(jié)點(diǎn)的節(jié)點(diǎn)。
示例:
給定二叉樹 [3,9,20,null,null,15,7],
3/ \9 20/ \15 7
返回它的最大深度 3 。
題目要求找出二叉樹的最大深度,因此可以通過深度優(yōu)先搜索的方式,而且推薦使用后序遍歷來遍歷二叉樹,記錄每個(gè)節(jié)點(diǎn)的深度,然后返回最大深度即可。
具體實(shí)現(xiàn)時(shí),可以編寫一個(gè)遞歸函數(shù) maxDepth
,該函數(shù)接受一個(gè)參數(shù) node
,表示當(dāng)前節(jié)點(diǎn)。如果當(dāng)前節(jié)點(diǎn)為空,則返回 0;否則,分別遞歸遍歷當(dāng)前節(jié)點(diǎn)的左右子樹,返回左右子樹深度的較大值加上 1,即為當(dāng)前節(jié)點(diǎn)的深度。
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = Noneclass Solution(object):def maxDepth(self, root):# 如果二叉樹為空,則返回 0if not root:return 0# 分別遞歸遍歷當(dāng)前節(jié)點(diǎn)的左右子樹left_depth = self.maxDepth(root.left)right_depth = self.maxDepth(root.right)# 返回左右子樹深度的較大值加上 1,即為當(dāng)前節(jié)點(diǎn)的深度return max(left_depth, right_depth) + 1
四、二叉樹的最小深度
給定一個(gè)二叉樹,找出其最小深度。
最小深度是從根節(jié)點(diǎn)到最近葉子節(jié)點(diǎn)的最短路徑上的節(jié)點(diǎn)數(shù)量。
**說明:**葉子節(jié)點(diǎn)是指沒有子節(jié)點(diǎn)的節(jié)點(diǎn)。
示例 1:
輸入:root = [3,9,20,null,null,15,7]
輸出:2
示例 2:
輸入:root = [2,null,3,null,4,null,5,null,6]
輸出:5
提示:
- 樹中節(jié)點(diǎn)數(shù)的范圍在
[0, 105]
內(nèi) -1000 <= Node.val <= 1000
題目要求找出二叉樹的最小深度,因此我媽可以通過深度優(yōu)先搜索的方式來遍歷二叉樹,記錄每個(gè)節(jié)點(diǎn)的深度,然后返回最小深度即可。
具體實(shí)現(xiàn)時(shí),可以編寫一個(gè)遞歸函數(shù) minDepth
,該函數(shù)接受一個(gè)參數(shù) node
,表示當(dāng)前節(jié)點(diǎn)。如果當(dāng)前節(jié)點(diǎn)為空,則返回 0;否則,分別遞歸遍歷當(dāng)前節(jié)點(diǎn)的左右子樹,如果當(dāng)前節(jié)點(diǎn)有左右子樹,則返回左右子樹深度的較小值加上 1,否則返回左右子樹深度的較大值加上 1,即為當(dāng)前節(jié)點(diǎn)的深度。
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = Noneclass Solution(object):def minDepth(self, root):# 如果二叉樹為空,則返回 0if not root:return 0# 分別遞歸遍歷當(dāng)前節(jié)點(diǎn)的左右子樹left_depth = self.minDepth(root.left)right_depth = self.minDepth(root.right)if not root.left or not root.right:# 如果當(dāng)前節(jié)點(diǎn)只有一個(gè)子節(jié)點(diǎn),則返回另一個(gè)子樹的深度加上 1return left_depth + right_depth + 1else:# 如果當(dāng)前節(jié)點(diǎn)有左右子樹,則返回左右子樹深度的較小值加上 1return min(left_depth, right_depth) + 1
這里需要注意的是,在計(jì)算當(dāng)前節(jié)點(diǎn)只有一個(gè)子節(jié)點(diǎn)的情況時(shí),我們需要將其另一個(gè)子樹的深度加上 1,因?yàn)楫?dāng)前節(jié)點(diǎn)不是葉子節(jié)點(diǎn),而是只有一個(gè)子節(jié)點(diǎn)的非葉子節(jié)點(diǎn)。
五、完全二叉樹的節(jié)點(diǎn)個(gè)數(shù)
給你一棵 完全二叉樹 的根節(jié)點(diǎn) root ,求出該樹的節(jié)點(diǎn)個(gè)數(shù)。
完全二叉樹 的定義如下:在完全二叉樹中,除了最底層節(jié)點(diǎn)可能沒填滿外,其余每層節(jié)點(diǎn)數(shù)都達(dá)到最大值,并且最下面一層的節(jié)點(diǎn)都集中在該層最左邊的若干位置。若最底層為第 h 層,則該層包含 1~ 2h 個(gè)節(jié)點(diǎn)。
示例 1:
輸入:root = [1,2,3,4,5,6]
輸出:6
示例 2:
輸入:root = []
輸出:0
示例 3:
輸入:root = [1]
輸出:1
提示:
- 樹中節(jié)點(diǎn)的數(shù)目范圍是
[0, 5 * 104]
0 <= Node.val <= 5 * 104
- 題目數(shù)據(jù)保證輸入的樹是 完全二叉樹
**進(jìn)階:**遍歷樹來統(tǒng)計(jì)節(jié)點(diǎn)是一種時(shí)間復(fù)雜度為 O(n)
的簡單解決方案。你可以設(shè)計(jì)一個(gè)更快的算法嗎?
在這里我們可以直接當(dāng)作普通二叉樹來處理,也就是之前練習(xí)的層序遍歷,直接使用那個(gè)模板,記錄遍歷的節(jié)點(diǎn)數(shù)量就可以了。
在這里我們主要來著重利用完全二叉樹的性質(zhì)來解決問題,由于完全二叉樹的特殊性質(zhì),我們可以先分別求出左子樹和右子樹的高度,然后根據(jù)它們的高度分情況討論。
- 如果左右子樹的高度相同,說明左子樹是一棵滿二叉樹,右子樹是一棵完全二叉樹,那么左子樹的節(jié)點(diǎn)個(gè)數(shù)可以直接計(jì)算,右子樹的節(jié)點(diǎn)個(gè)數(shù)可以遞歸地求解。
- 如果左右子樹的高度不同,說明右子樹是一棵滿二叉樹,左子樹是一棵完全二叉樹,那么右子樹的節(jié)點(diǎn)個(gè)數(shù)可以直接計(jì)算,左子樹的節(jié)點(diǎn)個(gè)數(shù)可以遞歸地求解。
最終,根據(jù)上述討論的結(jié)果,我們可以遞歸地求解出完全二叉樹的節(jié)點(diǎn)個(gè)數(shù)。
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = Noneclass Solution(object):def countNodes(self, root):if not root:return 0# 分別求出左子樹和右子樹的高度left_height = self.get_height(root.left)right_height = self.get_height(root.right)# 如果左右子樹的高度相同,說明左子樹是一棵滿二叉樹,右子樹是一棵完全二叉樹if left_height == right_height:# 左子樹的節(jié)點(diǎn)個(gè)數(shù)可以直接計(jì)算return (1 << left_height) + self.countNodes(root.right)# 如果左右子樹的高度不同,說明右子樹是一棵滿二叉樹,左子樹是一棵完全二叉樹else:# 右子樹的節(jié)點(diǎn)個(gè)數(shù)可以直接計(jì)算return (1 << right_height) + self.countNodes(root.left)def get_height(self, node):height = 0while node:height += 1node = node.leftreturn height
我們也可以換一個(gè)實(shí)現(xiàn)思路,首先判斷二叉樹是否為空,若為空則節(jié)點(diǎn)個(gè)數(shù)為0,直接返回;否則,記錄左子樹和右子樹的根節(jié)點(diǎn),同時(shí)記錄左子樹和右子樹的深度,初始值都為0。
接著,通過循環(huán),不斷地遍歷左子樹和右子樹,直到無法遍歷,統(tǒng)計(jì)出左子樹和右子樹的深度。
如果左子樹的深度等于右子樹的深度,說明左子樹是滿二叉樹,右子樹是完全二叉樹,此時(shí)可以利用滿二叉樹的節(jié)點(diǎn)數(shù)公式計(jì)算出總節(jié)點(diǎn)數(shù),即 2leftDepth+1?12^{leftDepth+1}-12leftDepth+1?1,其中 leftDepthleftDepthleftDepth 表示左子樹的深度。
如果左子樹的深度不等于右子樹的深度,說明左子樹是完全二叉樹,右子樹是滿二叉樹,此時(shí)可以遞歸計(jì)算左子樹和右子樹的節(jié)點(diǎn)個(gè)數(shù),并將它們加起來再加上根節(jié)點(diǎn),即可得到總節(jié)點(diǎn)數(shù)。
最終返回計(jì)算出的節(jié)點(diǎn)數(shù)即可。
class Solution:def countNodes(self, root) -> int:if not root:return 0left = root.leftright = root.rightleftDepth = 0 #這里初始為0是有目的的,為了下面求指數(shù)方便rightDepth = 0while left: #求左子樹深度left = left.leftleftDepth += 1while right: #求右子樹深度right = right.rightrightDepth += 1if leftDepth == rightDepth:return (2 << leftDepth) - 1 #注意(2<<1) 相當(dāng)于2^2,所以leftDepth初始為0return self.countNodes(root.left) + self.countNodes(root.right) + 1
六、平衡二叉樹
給定一個(gè)二叉樹,判斷它是否是高度平衡的二叉樹。
本題中,一棵高度平衡二叉樹定義為:
一個(gè)二叉樹每個(gè)節(jié)點(diǎn) 的左右兩個(gè)子樹的高度差的絕對(duì)值不超過 1 。
示例 1:
輸入:root = [3,9,20,null,null,15,7]
輸出:true
示例 2:
輸入:root = [1,2,2,3,3,null,null,4,4]
輸出:false
示例 3:
輸入:root = []
輸出:true
提示:
- 樹中的節(jié)點(diǎn)數(shù)在范圍
[0, 5000]
內(nèi) -104 <= Node.val <= 104
首先我們需要思考的是對(duì)于一棵二叉樹,如果它是一棵空樹,則它是平衡二叉樹,因?yàn)樗鼪]有任何節(jié)點(diǎn),高度為0。
接著,我們可以通過遞歸的方式判斷以每個(gè)節(jié)點(diǎn)為根的子樹是否是平衡二叉樹。
對(duì)于每個(gè)節(jié)點(diǎn),我們需要計(jì)算它的左子樹和右子樹的高度,并判斷它們的高度差是否大于1,如果大于1,則說明該節(jié)點(diǎn)的子樹不是平衡二叉樹;否則,遞歸判斷它的左子樹和右子樹是否是平衡二叉樹,如果左子樹和右子樹都是平衡二叉樹,則該節(jié)點(diǎn)的子樹也是平衡二叉樹。
最終,如果整個(gè)二叉樹是平衡二叉樹,則返回True,否則返回False。
class Solution:def isBalanced(self, root) -> bool:# 調(diào)用方法 getHeight 來獲取二叉樹的高度if self.getHeight(root) != -1:return Trueelse:return Falsedef getHeight(self, root):# 如果當(dāng)前節(jié)點(diǎn)是空節(jié)點(diǎn),則返回0if not root:return 0# 分別計(jì)算當(dāng)前節(jié)點(diǎn)的左右子樹的高度# 如果左右子樹的高度差大于1,則說明該節(jié)點(diǎn)不是平衡二叉樹,返回-1# 否則,返回該節(jié)點(diǎn)的高度if (leftHeight := self.getHeight(root.left)) == -1:return -1if (rightHeight := self.getHeight(root.right)) == -1:return -1if abs(leftHeight - rightHeight) > 1:return -1else:return 1 + max(leftHeight, rightHeight)