樹

力扣102：二叉搜索樹的層次遍歷

力扣105：從前序和中序重構二叉樹

力扣108：將有序數組轉化為二叉搜索樹

力扣110：平衡二叉樹

力扣113：路徑總和

力扣124：二叉樹的最大路徑和

力扣1325：刪除給定值的葉子節點

力扣144：二叉樹的前序遍歷（非遞歸）

力扣145：二叉樹的后續遍歷（非遞歸）

力扣199：二叉樹的右視圖

力扣208：實現Trie前綴樹

力扣222：完全二叉樹的節點數

力扣226：翻轉二叉樹

力扣236：二叉樹的最近公共祖先

力扣257：二叉樹的所有路徑

力扣297：二叉樹的序列化和反序列化

力扣450：刪除二叉樹中的節點

力扣543：二叉樹的直徑長度

力扣617：合并二叉樹

力扣662：二叉樹的最大寬度

力扣687：最長同值路徑

力扣94：二叉樹中序遍歷（非遞歸）

力扣958：二叉樹的完全性檢驗

力扣98：驗證二叉搜索樹

力扣99：恢復二叉搜索樹

重建二叉樹

Z字形層次遍歷

知識點

• 掌握二叉樹遞歸與非遞歸遍歷
• 理解 DFS 前序遍歷與分治法
• 理解 BFS 層次遍歷

二叉樹遍歷

• 前序遍歷：先訪問根節點，再前序遍歷左子樹，再前序遍歷右子樹
• 中序遍歷：先中序遍歷左子樹，再訪問根節點，再中序遍歷右子樹
• 后序遍歷：先后序遍歷左子樹，再后序遍歷右子樹，再訪問根節點

注意點

• 以根訪問順序決定是什么遍歷
• 左子樹都是優先右子樹

遞歸模板

• 遞歸實現二叉樹遍歷非常簡單，不同順序區別僅在于訪問父結點順序

def preorder_rec(root):if root is None:returnvisit(root)preorder_rec(root.left)preorder_rec(root.right)returndef inorder_rec(root):if root is None:returninorder_rec(root.left)visit(root)inorder_rec(root.right)returndef postorder_rec(root):if root is None:returnpostorder_rec(root.left)postorder_rec(root.right)visit(root)return

前序非遞歸

• 本質上是圖的DFS的一個特例，因此可以用棧來實現

class Solution:def preorderTraversal(self, root: TreeNode) -> List[int]:if not root: return []res, stack = [], [root] # 利用棧進行臨時存儲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

中序非遞歸

中序遍歷的思想是：
1.若節點還有左子樹，就要把左子樹訪問完；
2.沒有左子樹可以訪問時，訪問該節點，并嘗試訪問右子樹

class Solution:def inorderTraversal(self, root: TreeNode) -> List[int]:s, inorder = [], []node = rootwhile len(s) > 0 or node is not None:if node is not None:s.append(node)node = node.leftelse:node = s.pop()inorder.append(node.val)node = node.rightreturn inorder

后序非遞歸

后序遍歷（迭代法）

再來看后序遍歷，先序遍歷是中左右，后續遍歷是左右中，那么我們只需要調整一下先序遍歷的代碼順序，就變成中右左的遍歷順序，然后在反轉result數組，輸出的結果順序就是左右中了，如下圖：

所以后序遍歷只需要前序遍歷的代碼稍作修改就可以了，代碼如下：

# Definition for a binary tree node. # class TreeNode(object): # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution:def postorderTraversal(self, root):preorder = []if root is None:return preorders = [root]while len(s) > 0:node = s.pop()preorder.append(node.val)if node.left is not None:s.append(node.left)if node.right is not None:s.append(node.right)return preorder[::-1] # Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution:def postorderTraversal(self, root: TreeNode) -> List[int]:stack, node = [], rootprev = Noneres = []if not root: return [] # 基本情況直接返回while node or stack:while node: # 走到左分支的盡頭stack.append(node)node = node.leftnode = stack.pop()if not node.right or node.right == prev: # 如果左分支的盡頭沒有右子節點，就應該把它放進去res.append(node.val)prev = node # 記錄母節點node = Noneelse:stack.append(node) # 如果有右子節點，放到stack里面，有點像dfsnode = node.rightreturn res

后續遍歷的主要特點是：遍歷左分支的左右根節點，再把左分支的主干節點逐個返回。

注意點

• 核心就是：根節點必須在右節點彈出之后，再彈出

class Solution:def postorderTraversal(self, root: TreeNode) -> List[int]:s, postorder = [], []node, last_visit = root, Nonewhile len(s) > 0 or node is not None:if node is not None:s.append(node)node = node.leftelse:peek = s[-1]if peek.right is not None and last_visit != peek.right:node = peek.rightelse:last_visit = s.pop()postorder.append(last_visit.val)return postorder

分治法應用

先分別處理局部，再合并結果

適用場景

• 快速排序
• 歸并排序
• 二叉樹相關問題

分治法模板

• 遞歸返回條件
• 分段處理
• 合并結果

104. 二叉樹的最大深度

給定一個二叉樹，找出其最大深度。

class Solution:def maxDepth(self, root: TreeNode) -> int:if not root:return 0return 1 + max([self.maxDepth(root.left), self.maxDepth(root.right)])

• 思路 2：層序遍歷

class Solution:def maxDepth(self, root: TreeNode) -> List[List[int]]:depth = 0if root is None:return depthbfs = collections.deque([root])while len(bfs) > 0:depth += 1level_size = len(bfs)for _ in range(level_size):node = bfs.popleft()if node.left is not None:bfs.append(node.left)if node.right is not None:bfs.append(node.right)return depth

94. 二叉樹的中序遍歷

給定一個二叉樹的根節點root，返回它的中序 遍歷。

示例 1：

1\2/ 3 輸出：[1,3,2]

思路：經典遞歸.

class Solution:def preorderTraversal(self, root: TreeNode) -> List[int]:if root is None:return []left_result = self.preorderTraversal(root.left)right_result = self.preorderTraversal(root.right)return [root.val] + left_result + right_result class Solution:def inorderTraversal(self, root: TreeNode) -> List[int]:if not root:return []return self.inorderTraversal(root.left) + [root.val] + self.inorderTraversal(root.right)

98. 驗證二叉搜索樹

給定一個二叉樹，判斷其是否是一個有效的二叉搜索樹。

思路：

得到中序遍歷的結果；

判斷中序遍歷是否單調遞增。

class Solution:def isValidBST(self, root: TreeNode) -> bool:def get_mfs(root):if not root:return []return get_mfs(root.left) +[root.val] + get_mfs(root.right)?res = get_mfs(root) if len(res) <= 1:return Truefor i in range(1,len(res)):if res[i] <= res[i-1]:return Falsereturn True

分治法: 一個二叉樹為合法的二叉搜索樹當且僅當左右子樹為合法二叉搜索樹且根結點值大于右子樹最小值小于左子樹最大值。

# Definition for a binary tree node. # class TreeNode(object): # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution:def isValidBST(self, root):if root is None: return Truedef valid_min_max(node):isValid = Trueif node.left is not None:l_isValid, l_min, l_max = valid_min_max(node.left)isValid = isValid and node.val > l_maxelse:l_isValid, l_min = True, node.valif node.right is not None:r_isValid, r_min, r_max = valid_min_max(node.right)isValid = isValid and node.val < r_minelse:r_isValid, r_max = True, node.valreturn l_isValid and r_isValid and isValid, l_min, r_maxreturn valid_min_max(root)[0] class Solution:def isValidBST(self, root: TreeNode) -> bool:if root is None:return Trues = [(root, float('-inf'), float('inf'))]while len(s) > 0:node, low, up = s.pop()if node.left is not None:if node.left.val <= low or node.left.val >= node.val:return Falses.append((node.left, low, node.val))if node.right is not None:if node.right.val <= node.val or node.right.val >= up:return Falses.append((node.right, node.val, up))return True

543. 二叉樹的直徑

給定一棵二叉樹，你需要計算它的直徑長度。一棵二叉樹的直徑長度是任意兩個結點路徑長度中的最大值。這條路徑可能穿過也可能不穿過根結點。

class Solution:def diameterOfBinaryTree(self, root: TreeNode) -> int:self.ans = 1def depth(node):# 訪問到空節點了，返回0if not node:return 0# 左兒子為根的子樹的深度L = depth(node.left)# 右兒子為根的子樹的深度R = depth(node.right)# 計算d_node即L+R+1 并更新ansself.ans = max(self.ans, L + R + 1)# 返回該節點為根的子樹的深度return max(L, R) + 1depth(root)return self.ans - 1

102. 二叉樹的層序遍歷

給你一個二叉樹，請你返回其按 層序遍歷 得到的節點值。 （即逐層地，從左到右訪問所有節點）。

示例：

3/ \9 20/ \15 7

返回其層序遍歷結果：

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

思路：二叉樹的題目很多適合用遞歸，因為二叉樹本身就是由相同的節點結構組成。而此題用迭代實現更直觀。

# Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution:def levelOrder(self, root: TreeNode) -> List[List[int]]:if not root: return []#跟結點入queuequeue = [root]res = []while queue:res.append([node.val for node in queue])#存儲當前層的孩子節點列表ll = []#對當前層的每個節點遍歷for node in queue:#如果左子節點存在，入隊列if node.left:ll.append(node.left)#如果右子節點存在，入隊列if node.right:ll.append(node.right)#后把queue更新成下一層的結點，繼續遍歷下一層queue = llreturn res

對于題目199，右視圖即每層最右邊的值，因此只需要做一個非常簡單的小變化，即返回的列表只需要對每一層的列表的最后一個元素入結果列表就可以了

#只需要對該層最后一個元素入列表 res.append([node.val for node in queue][-1]) # Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution:def rightSideView(self, root: TreeNode) -> List[int]:if not root: return []#跟結點入queuequeue = [root]res = []while queue:#只需要對該層最后一個元素入列表res.append([node.val for node in queue][-1])#存儲當前層的孩子節點列表ll = []#對當前層的每個節點遍歷for node in queue:#如果左子節點存在，入隊列if node.left:ll.append(node.left)#如果右子節點存在，入隊列if node.right:ll.append(node.right)#后把queue更新成下一層的結點，繼續遍歷下一層queue = llreturn res

insert-into-a-binary-search-tree

給定二叉搜索樹（BST）的根節點和要插入樹中的值，將值插入二叉搜索樹。 返回插入后二叉搜索樹的根節點。 保證原始二叉搜索樹中不存在新值。

class Solution:def insertIntoBST(self, root: TreeNode, val: int) -> TreeNode:if root is None:return TreeNode(val)if val > root.val:root.right = self.insertIntoBST(root.right, val)else:root.left = self.insertIntoBST(root.left, val)return root

437. 路徑總和 III

給定一個二叉樹，它的每個結點都存放著一個整數值。

找出路徑和等于給定數值的路徑總數。

路徑不需要從根節點開始，也不需要在葉子節點結束，但是路徑方向必須是向下的（只能從父節點到子節點）。

基本思路：先回溯得到以根節點為起點(一定包含根節點)的路徑和滿足要求的總數。再深度優先搜索，即根節點路徑數目+左節點路徑數目+右節點路徑數目

class Solution:def pathSum(self, root: TreeNode, targetSum: int) -> int:def backtrace(root, sum):res = 0if not root:return resif sum == root.val:res += 1if root.left:res += backtrace(root.left, sum - root.val)if root.right:res += backtrace(root.right, sum - root.val)return res# 返回路徑和等于數值的路徑數def DFS(root):if not root:return 0root_count = backtrace(root, targetSum)left_root = DFS(root.left)right_root = DFS(root.right)return left_root+right_root+root_countreturn DFS(root)

617. 合并二叉樹

給定兩個二叉樹，想象當你將它們中的一個覆蓋到另一個上時，兩個二叉樹的一些節點便會重疊。

你需要將他們合并為一個新的二叉樹。合并的規則是如果兩個節點重疊，那么將他們的值相加作為節點合并后的新值，否則不為 NULL 的節點將直接作為新二叉樹的節點。

示例 1:

輸入: Tree 1 Tree 2 1 2 / \ / \ 3 2 1 3 / \ \ 5 4 7 輸出: 合并后的樹:3/ \4 5/ \ \ 5 4 7 注意: 合并必須從兩個樹的根節點開始。

思路：經典左右遞歸

class Solution:def mergeTrees(self, t1: TreeNode, t2: TreeNode) -> TreeNode:if not t2:return t1elif not t1:return t2else:t3 = TreeNode()t3.val = t1.val + t2.valt3.left = self.mergeTrees(t1.left,t2.left)t3.right = self.mergeTrees(t1.right,t2.right)return t3

226. 翻轉二叉樹

左右翻轉一棵二叉樹。

思路：經典左右遞歸

class Solution:def invertTree(self, root: TreeNode) -> TreeNode:if not root:returnroot.left, root.right = self.invertTree(root.right), self.invertTree(root.left)return root

114. 二叉樹展開為鏈表

給定一個二叉樹，原地將它展開為一個單鏈表。

1/ \2 5/ \ \ 3 4 6

將其展開為：

1\2\3\4\5\6

思路：前序遍歷。

class Solution:def flatten(self, root: TreeNode) -> None:if not root:return# 先把左右兩個子樹處理成鏈表self.flatten(root.left)self.flatten(root.right)# 接下來把右邊鏈表剝離，把左邊鏈表掛在root.righttmp_right = root.rightroot.right = root.leftroot.left = None# 然后把右邊鏈表掛在原左邊鏈表的最后while root.right!=None:root = root.right # 找到原左鏈表的末尾，用于接右鏈表root.right = tmp_right

96. 不同的二叉搜索樹

給定一個整數n，求以 1 ... n 為節點組成的二叉搜索樹有多少種？

思路：

class Solution:def numTrees(self, n):""":type n: int:rtype: int"""G = [0]*(n+1)G[0], G[1] = 1, 1for i in range(2, n+1):for j in range(1, i+1):G[i] += G[j-1] * G[i-j]return G[n]

時間復雜度 : O(n^2)，其中 n表示二叉搜索樹的節點個數。G(n)函數一共有 n 個值需要求解，每次求解需要 O(n) 的時間復雜度，因此總時間復雜度為 O(n^2)

空間復雜度 : O(n)。我們需要 O(n)的空間存儲 G 數組。

105. 從前序與中序遍歷序列構造二叉樹

根據一棵樹的前序遍歷與中序遍歷構造二叉樹, 樹中沒有重復的元素。

例如：

前序遍歷 preorder = [3,9,20,15,7] 中序遍歷 inorder = [9,3,15,20,7] 返回：3/ \9 20/ \15 7

思路：前序遍歷[根節點，左子樹，右子樹]，中序遍歷[左子樹，根節點，右子樹]，顯然前序遍歷第一個為根節點，根據根節點在中序遍歷中定位左右子樹的中序遍歷，同時可知左右子樹的元素數量，由此在前序遍歷中找到左右子樹的前序遍歷。由此遞歸。

class Solution:def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:if not preorder:returnroot = TreeNode()root.val = preorder[0]index = inorder.index(root.val)root.left = self.buildTree(preorder[1:index+1],inorder[:index])root.right = self.buildTree(preorder[index+1:],inorder[index+1:])return root

236. 二叉樹的最近公共祖先

給定一個二叉樹, 找到該樹中兩個指定節點的最近公共祖先。

所有節點的值都是唯一的。
p、q 為不同節點且均存在于給定的二叉樹中。

思路：

某節點是公共祖先有兩種情況：

該節點為指定節點中的一個，且子樹中存在另一個節點。

該節點不是指定節點，但其左右子樹均存在指定節點。

class Solution:def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':if not root:returnif root==q or root==p:return root # 可能為情況1，也可能是情況1中的子樹left = self.lowestCommonAncestor(root.left,p,q)right = self.lowestCommonAncestor(root.right,p,q)if left and right:return root # 情況2if not left:return rightif not right:return left

538. 把二叉搜索樹轉換為累加樹

給出二叉搜索樹的根節點，該樹的節點值各不相同，請你將其轉換為累加樹（Greater Sum Tree），使每個節點 node 的新值等于原樹中大于或等于node.val的值之和。

思路：

本題中要求我們將每個節點的值修改為原來的節點值加上所有大于它的節點值之和。這樣我們只需要反序中序遍歷該二叉搜索樹，記錄過程中的節點值之和，并不斷更新當前遍歷到的節點的節點值，即可得到題目要求的累加樹。

其實這就是一棵樹，大家可能看起來有點別扭，換一個角度來看，這就是一個有序數組[2, 5, 13]，求從后到前的累加數組，也就是[20, 18, 13]，大家是不是感覺這就是送分題了。

為什么變成數組就是送分題了呢，因為數組大家都知道怎么遍歷啊，從后向前，挨個累加就完事了，這換成了二叉搜索樹，看起來就別扭了一些是不是。

那么知道如何遍歷這個二叉樹，也就迎刃而解了，從樹中可以看出累加的順訊是 右中左，所以我們需要中序遍歷反過來遍歷這個二叉樹，然后順序累加就可以了。

class Solution:def __init__(self):self.accum = 0def convertBST(self, root: TreeNode) -> TreeNode:if not root:return # 接下來逆中序遍歷rootself.convertBST(root.right) # 1. 遍歷右子樹root.val += self.accum # 2. 遍歷當前結點self.accum = root.val self.convertBST(root.left) # 3. 遍歷左子樹return root

337. 打家劫舍 III

二叉樹的每個節點數字代表屋子中的金額，如果兩個直接相連的房子在同一天晚上被打劫，房屋將自動報警。計算在不觸動警報的情況下，小偷一晚能夠盜取的最高金額。

示例：

輸入: [3,4,5,1,3,null,1]3/ \4 5/ \ \ 1 3 1輸出: 9 解釋: 小偷一晚能夠盜取的最高金額 = 4 + 5 = 9.

思路：

這道題目和 198.打家劫舍，213.打家劫舍II 如出一轍，只不過這個換成了樹。

如果對樹的遍歷不夠熟悉的話，那本題就有難度了。

對于樹的話，首先就要想到遍歷方式，前中后序（深度優先搜索）還是層序遍歷（廣度優先搜索）。

本題一定是要后序遍歷，因為通過遞歸函數的返回值來做下一步計算。

與198.打家劫舍，213.打家劫舍II 一樣，關鍵是要討論當前節點搶還是不搶。

如果搶了當前節點，兩個孩子就不是動，如果沒搶當前節點，就可以考慮搶左右孩子（注意這里說的是“考慮”）

動態規劃其實就是使用狀態轉移容器來記錄狀態的變化，這里可以使用一個長度為2的數組，記錄當前節點偷與不偷所得到的的最大金錢。

1.確定遞歸函數的參數和返回值

這里我們要求一個節點 偷與不偷的兩個狀態所得到的金錢，那么返回值就是一個長度為2的數組。

??????? def rob_tree(root):
??????????? '''
??????????? 返回一個元組(rob, skip)，分別代表偷root節點的總收益，和不偷的總收益。
??????????? 總收益的意思是以root為根節點的子樹的總收益。
??????????? '''

所以dp數組（dp table）以及下標的含義：下標為0記錄不偷該節點所得到的的最大金錢，下標為1記錄偷該節點所得到的的最大金錢。所以本題dp數組就是一個長度為2的數組！

那么有同學可能疑惑，長度為2的數組怎么標記樹中每個節點的狀態呢？

別忘了在遞歸的過程中，系統棧會保存每一層遞歸的參數。

如果還不理解的話，就接著往下看，看到代碼就理解了哈。

2 確定終止條件

在遍歷的過程中，如果遇到空間點的話，很明顯，無論偷還是不偷都是0，所以就返回
??????????? if not root:
??????????????? return (0,0) # (偷當前節點金額，不偷當前節點金額)

這也相當于dp數組的初始化

3.確定遍歷順序

首先明確的是使用后序遍歷。 因為通過遞歸函數的返回值來做下一步計算。

a.通過遞歸左節點，得到左節點偷與不偷的金錢。

b.通過遞歸右節點，得到右節點偷與不偷的金錢。

??????????? left_subtree = rob_tree(root.left)
??????????? right_subtree = rob_tree(root.right)

?4. 確定單層遞歸的邏輯

如果是偷當前節點，那么左右孩子就不能偷，val1 = cur->val + left[0] + right[0]; （如果對下標含義不理解就在回顧一下dp數組的含義）

如果不偷當前節點，那么左右孩子就可以偷，至于到底偷不偷一定是選一個最大的，所以：val2 = max(left[0], left[1]) + max(right[0], right[1]);

最后當前節點的狀態就是{val2, val1}; 即：{不偷當前節點得到的最大金錢，偷當前節點得到的最大金錢}

對于每個節點，有兩種狀態：盜竊該節點和不盜竊。如果盜竊，則其左右子節點不能盜竊；如果不盜竊，則左右子節點也可以取兩種狀態。

最后頭結點就是 取下標0 和 下標1的最大值就是偷得的最大金錢。

class Solution:def rob(self, root: TreeNode) -> int:def rob_tree(root):'''返回一個元組(rob, skip)，分別代表偷root節點的總收益，和不偷的總收益。總收益的意思是以root為根節點的子樹的總收益。'''if not root:return (0,0) # (偷當前節點金額，不偷當前節點金額)# 考慮以root為根節點的子樹的收益, 偷了root就不能再偷左右子節點了left_subtree = rob_tree(root.left)right_subtree = rob_tree(root.right)rob = root.val + left_subtree[1] +right_subtree[1] # 偷當前節點，不能偷子節點skip = max(left_subtree[0], left_subtree[1]) + max(right_subtree[0], right_subtree[1]) # 不偷當前節點，可偷可不偷子節點return rob, skipresult = self.rob_tree(root)return max(result[0], result[1])

101. 對稱二叉樹

給定一個二叉樹，檢查它是否是鏡像對稱的。

思路：

遞歸思路：

class Solution:def isSymmetric(self, root: TreeNode) -> bool:def is_sym(a,b):if not a and not b:return Trueelif not a or not b:return Falseif a.val != b.val:return Falsereturn is_sym(a.left,b.right) and is_sym(a.right,b.left)if not root:return Truereturn is_sym(root.left,root.right)

迭代思路，一層一層遍歷，每層查看是否對稱：

class Solution:def isSymmetric(self, root: TreeNode) -> bool:if not root:return Truelayer = [root]while layer:vals = [root.val if root else None for root in layer ]if vals!=vals[::-1]:return Falselayer = [(root.left, root.right) for root in layer if root]layer = [i for tpl in layer for i in tpl]return True

297. 二叉樹的序列化與反序列化

將二叉樹轉化為字符串，并且可以將字符串再轉化為原始的二叉樹。

思路：

序列化的就是把數據結構轉為字符串，可以使用DFS的方式，二叉樹DFS的方法就是對每個節點，都先處理左子節點，再處理右子節點。

class Codec:def serialize(self, root):vals = []def dfs(node):if node:vals.append(str(node.val))dfs(node.left)dfs(node.right)else:vals.append("#")dfs(root)s = " ".join(vals)return sdef deserialize(self, data):def redfs():if vals:val = vals.pop(0)else:returnif val == "#":return Nonenode = TreeNode(int(val))node.left = redfs()node.right = redfs()return nodevals = data.split(" ")return redfs()

124. 二叉樹中的最大路徑和

路徑被定義為一條從樹中任意節點出發，沿父節點-子節點連接，達到任意節點的序列。該路徑 至少包含一個 節點，且不一定經過根節點。

路徑和 是路徑中各節點值的總和。

給你一個二叉樹的根節點 root ，返回其 最大路徑和 。

思路：

遞歸，對每個節點，最大值有四種情況：

僅該節點（比如左右子樹都是負數）

該節點加左子樹單鏈最大值

該節點加右子樹單鏈的最大值

該節點加左右子樹單鏈的最大值

class Solution:def recur(self,root):if not root:return 0left = self.recur(root.left)right = self.recur(root.right)tmpv = max(left+root.val, right+root.val, left + root.val + right, root.val)if tmpv > self.maxv:self.maxv = tmpvreturn max(left, right, 0) + root.valdef maxPathSum(self, root):self.maxv = root.val_ = self.recur(root)return self.maxv class Solution:def __init__(self):self.maxSum = float("-inf")def maxPathSum(self, root):def maxGain(node):if not node:return 0# 遞歸計算左右子節點的最大貢獻值# 只有在最大貢獻值大于 0 時，才會選取對應子節點leftGain = max(maxGain(node.left), 0)rightGain = max(maxGain(node.right), 0)# 節點的最大路徑和取決于該節點的值與該節點的左右子節點的最大貢獻值priceNewpath = node.val + leftGain + rightGain# 更新答案self.maxSum = max(self.maxSum, priceNewpath)# 返回節點的最大貢獻值return node.val + max(leftGain, rightGain)maxGain(root)return self.maxSum

balanced-binary-tree

給定一個二叉樹，判斷它是否是高度平衡的二叉樹。

• 思路 1：分治法，左邊平衡 && 右邊平衡 && 左右兩邊高度 <= 1

class Solution:def isBalanced(self, root: TreeNode) -> bool:def depth(root):if root is None:return 0, Truedl, bl = depth(root.left)dr, br = depth(root.right)return max(dl, dr) + 1, bl and br and abs(dl - dr) < 2_, out = depth(root)return out

insert-into-a-binary-search-tree

給定二叉搜索樹（BST）的根節點和要插入樹中的值，將值插入二叉搜索樹。 返回插入后二叉搜索樹的根節點。

• 思路：如果只是為了完成任務則找到最后一個葉子節點滿足插入條件即可。

class Solution:def insertIntoBST(self, root: TreeNode, val: int) -> TreeNode:if root is None:return TreeNode(val)node = rootwhile True:if val > node.val:if node.right is None:node.right = TreeNode(val)return rootelse:node = node.rightelse:if node.left is None:node.left = TreeNode(val)return rootelse:node = node.left

練習

• maximum-depth-of-binary-tree
• balanced-binary-tree
• binary-tree-maximum-path-sum
• lowest-common-ancestor-of-a-binary-tree
• binary-tree-level-order-traversal
• binary-tree-level-order-traversal-ii
• binary-tree-zigzag-level-order-traversal
• validate-binary-search-tree
• insert-into-a-binary-search-tree

創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的LeetCode Hot100 ---- 二叉树专题的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。