給你一棵二叉樹的根節(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)$，其中 $n$ 是二叉樹的節(jié)點(diǎn)個(gè)數(shù)，因?yàn)槊總€(gè)節(jié)點(diǎn)都會(huì)被訪問一次。空間復(fù)雜度為 $O(n)$，因?yàn)檫f歸函數(shù)會(huì)使用系統(tǒng)棧，最壞情況下系統(tǒng)棧的深度等于二叉樹的高度，即為 $O(n)$。

給你一個(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) 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ù)，即 $2^{leftDepth+1}?1$，其中 $leftDepth$ 表示左子樹的深度。

如果左子樹的深度不等于右子樹的深度，說明左子樹是完全二叉樹，右子樹是滿二叉樹，此時(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)