本博客的內(nèi)容只是做一個(gè)大概的記錄，整個(gè)PDF看下來(lái)，內(nèi)容上是不如代碼隨想錄網(wǎng)站上的文章全面的，并且PDF中有些地方的描述，是很讓我疑惑的，在困擾我很久后，無(wú)意間發(fā)現(xiàn)，其網(wǎng)站上的講解完全符合我的思路。這次看完這些PDF后，暫時(shí)一段時(shí)間內(nèi)不會(huì)再看了，要復(fù)習(xí)還是依靠，代碼隨想錄網(wǎng)站，視頻，和我自己寫的博客吧

二叉樹(shù)章節(jié)

二叉樹(shù)章節(jié)，做不出來(lái)的題基本上都有一個(gè)共性，對(duì)二叉樹(shù)的數(shù)據(jù)結(jié)構(gòu)特性不熟悉，從而沒(méi)有編寫思路，或者在判斷條件上產(chǎn)生疏漏。

完全二叉樹(shù)：除了最底層可能沒(méi)填滿，其余每層節(jié)點(diǎn)數(shù)都達(dá)到最大值，并且最下面一層的節(jié)點(diǎn)，都集中在該層最左邊的若干位置。一個(gè)很關(guān)鍵的點(diǎn)：完全二叉樹(shù)的某些子樹(shù)，一定是滿二叉樹(shù)，節(jié)點(diǎn)數(shù)量是可以計(jì)算的。去計(jì)算最左和最后，一直向左找，計(jì)數(shù)，一直向右找，計(jì)數(shù)，如果兩數(shù)相等，這顆子樹(shù)就是滿二叉樹(shù)。

二叉搜索樹(shù)：若它的左子樹(shù)不空，則左子樹(shù)上所有節(jié)點(diǎn)的值，均小于它的根節(jié)點(diǎn)的值。若它的右子樹(shù)不空，則右子樹(shù)上所有節(jié)點(diǎn)的值，均大于它的根節(jié)點(diǎn)的值。它的左右子樹(shù)也分別為二叉搜索樹(shù)。

平衡二叉樹(shù)：它是一個(gè)空樹(shù)，或者它的左右兩個(gè)子樹(shù)的高度差的絕對(duì)值不超過(guò)1，并且左右子樹(shù)都是一顆平衡二叉樹(shù)。

二叉樹(shù)的鏈?zhǔn)酱鎯?chǔ)，是大家一直在用的，那么其順序存儲(chǔ)，要注意，需要將樹(shù)填補(bǔ)為一顆滿二叉樹(shù)，才能滿足公式，如果父節(jié)點(diǎn)的數(shù)組下標(biāo)是 i , 那么它的左孩子就是 i2+1，右孩子是 i2+2 。

在遍歷方式上，主要分為兩大類，深度優(yōu)先遍歷（前中后序）遍歷，廣度優(yōu)先遍歷（層序遍歷）。層序遍歷有時(shí)候是很好用的方法，有的題，用遞歸解法較復(fù)雜，或者在代碼編寫邏輯上不好思考，后面會(huì)提到。

深度優(yōu)先遍歷的三種方法中，后序遍歷是應(yīng)用最多的，因?yàn)楹芏鄷r(shí)候，我們都需要去收集，左右子樹(shù)的信息，來(lái)決定當(dāng)前節(jié)點(diǎn)的方式，或者說(shuō)，需要將某些信息，一層一層地返回到根節(jié)點(diǎn)，這時(shí)候都需要后序遍歷。中序遍歷，和二叉搜索樹(shù)，嚴(yán)格綁定。前序遍歷需要的場(chǎng)景，一般都有比較明顯的特征，可以意識(shí)到。

前序遍歷：中左右；中序遍歷：左中右；后序遍歷：左右中。

二叉樹(shù)的節(jié)點(diǎn)定義：

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

遞歸三部曲

1、確定遞歸函數(shù)的參數(shù)和返回值。2、確定終止條件。3、確定單層遞歸的邏輯

判斷了遞歸中不會(huì)有空節(jié)點(diǎn)，就可以不寫返回條件？以前序遍歷為例

兩個(gè)版本代碼的對(duì)比，一個(gè)帶空節(jié)點(diǎn)判斷，一個(gè)不帶。

class Solution:def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:if root == None :return []self.res = []self.digui(root)return self.resdef digui(self,root):self.res.append(root.val)if root.left:self.digui(root.left)if root.right:self.digui(root.right)

class Solution:def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:if root == None :return []self.res = []self.digui(root)return self.resdef digui(self,root):if root == None :returnself.res.append(root.val)self.digui(root.left)self.digui(root.right)

二叉樹(shù)的迭代遍歷(一定要學(xué)會(huì))

前序遍歷：

class Solution:def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:if root == None :return []stack = [root]res = []while stack :node = stack.pop()res.append(node.val)# 注意，空節(jié)點(diǎn)不入棧if node.right :stack.append(node.right)if node.left :stack.append(node.left)return res

后序遍歷：

class Solution:def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:if root == None :return []stack = [root]res = []while stack :node = stack.pop()res.append(node.val)# 空節(jié)點(diǎn)不入棧if node.left:stack.append(node.left)if node.right:stack.append(node.right)# 代碼編寫順序是，中左右，但是因?yàn)槭褂玫氖菞?#xff0c;那么在res數(shù)組中的順序是，中右左，倒序，左右中return res[::-1]

中序遍歷：

class Solution:def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:if root == None :return []stack = []cur = rootres = []while stack or cur:# 同樣注意，空節(jié)點(diǎn)不入棧if cur :stack.append(cur)cur = cur.leftelse :cur = stack.pop()res.append(cur.val)cur = cur.rightreturn res

上面三種迭代方法，需要注意的共同點(diǎn)是：迭代法中，要保證，空節(jié)點(diǎn)不入棧。

前中后序遍歷的，統(tǒng)一迭代方法

以中序遍歷為例：因?yàn)槭堑?#xff0c;使用的是棧作為數(shù)據(jù)結(jié)構(gòu)，在代碼中的編寫順序，和在結(jié)果集中的保存順序，是不一樣的。代碼編寫是，右中左，結(jié)果集中就是，左中右

lass Solution:def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:if root == None :return []stack = [root]res = []while stack :node = stack.pop()if node == None :node = stack.pop()res.append(node.val)        else :# 當(dāng)node不是空節(jié)點(diǎn)時(shí)的操作，是關(guān)鍵# 要根據(jù)遍歷順序重新調(diào)整元素順序# 因?yàn)槭鞘褂枚褩?#xff0c;所以要從下向上看，左中右if node.right :  # 右stack.append(node.right)stack.append(node) # 中stack.append(None)if node.left : # 左stack.append(node.left)return res

二叉樹(shù)的層序遍歷

層序遍歷是有標(biāo)準(zhǔn)寫法的。代碼隨想錄中列出的，與層序遍歷相關(guān)的10道題，都是稍微修改就可以做出來(lái)的。

class Solution:def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:if root == None :return []dq = deque()dq.append(root)res = []level = []while dq :size = len(dq)for i in range(size):node = dq.popleft()level.append(node.val)if node.left :dq.append(node.left)if node.right :dq.append(node.right)res.append(level)level = []return res

117. 填充每個(gè)節(jié)點(diǎn)的下一個(gè)右側(cè)節(jié)點(diǎn)指針 II

以層序遍歷為模板。

from collections import deque
class Solution:def connect(self, root: 'Node') -> 'Node':if root == None :return rootdq = deque()dq.append(root)pre = Nonewhile dq :size = len(dq)for i in range(size):if i == 0 :pre = dq.popleft()else :node = dq.popleft()pre.next = nodepre = nodeif pre.left :dq.append(pre.left)if pre.right :dq.append(pre.right)return root

104.二叉樹(shù)的最大深度

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

111.二叉樹(shù)的最小深度

需要注意的是，只有當(dāng)左右孩子都為空的時(shí)候，才說(shuō)明遍歷的最低點(diǎn)了。如果其中一個(gè)孩子為空則不是最低點(diǎn).

class Solution:def minDepth(self, root: TreeNode) -> int:if not root:return 0depth = 0queue = collections.deque([root])while queue:depth += 1 for _ in range(len(queue)):node = queue.popleft()if not node.left and not node.right:return depthif node.left:queue.append(node.left)if node.right:queue.append(node.right)return depth

上面求最大深度和最小深度的題目，我們后面還會(huì)遇到，可以發(fā)現(xiàn)，其實(shí)遞歸也不一定比迭代法好用，只不過(guò)能不能想的到，使用層序遍歷，就是需要修煉的了。

226.翻轉(zhuǎn)二叉樹(shù)，通過(guò)本題，希望學(xué)會(huì)，如何將遞歸方法中的邏輯，寫在相對(duì)應(yīng)的迭代法中

本題用什么遍歷順序？

對(duì)于使用基于遞歸的方法來(lái)說(shuō)：前序，后序，層序，都可以。唯獨(dú)中序不行。這個(gè)自己畫畫圖就可以知道。

對(duì)于使用迭代的方法來(lái)說(shuō)：同遞歸。（這里的迭代，指的是，不加入None的迭代法）

對(duì)于使用統(tǒng)一方式迭代的方法來(lái)說(shuō)：任何順序都可以。

遞歸代碼，前序遍歷：

class Solution:def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:if root == None :return rootroot.left , root.right = root.right, root.leftself.invertTree(root.left)self.invertTree(root.right)return root

遞歸代碼，中序遍歷：

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

迭代代碼，中序遍歷：

class Solution:def invertTree(self, root: TreeNode) -> TreeNode:if not root:return None      stack = [root]        while stack:node = stack.pop()                   if node.left:stack.append(node.left)node.left, node.right = node.right, node.left               if node.left:stack.append(node.left)       return root

迭代代碼，前序遍歷：

class Solution:def invertTree(self, root: TreeNode) -> TreeNode:if not root:return None      stack = [root]        while stack:node = stack.pop()   node.left, node.right = node.right, node.left                   if node.left:stack.append(node.left)if node.right:stack.append(node.right)  return root

統(tǒng)一迭代風(fēng)格的C++代碼，中序遍歷：

class Solution {
public:TreeNode* invertTree(TreeNode* root) {stack<TreeNode*> st;if (root != NULL) st.push(root);while (!st.empty()) {TreeNode* node = st.top();if (node != NULL) {st.pop();if (node->right) st.push(node->right);  // 右st.push(node);                          // 中st.push(NULL);if (node->left) st.push(node->left);    // 左} else {st.pop();node = st.top();st.pop();swap(node->left, node->right);          // 節(jié)點(diǎn)處理邏輯}}return root;}
};

為什么這個(gè)中序就是可以的呢，因?yàn)檫@是用棧來(lái)遍歷，而不是靠指針來(lái)遍歷，避免了遞歸法中翻轉(zhuǎn)了兩次的情況。

只要是能編寫出相應(yīng)迭代法的遞歸法，在時(shí)間復(fù)雜度上二者差不多，在空間復(fù)雜度上，迭代法要優(yōu)于遞歸。因?yàn)檫f歸需要系統(tǒng)堆棧存儲(chǔ)參數(shù)，返回值等信息。

通過(guò)上一題，我們要意識(shí)到，非統(tǒng)一版本的迭代法，前序和后序都是基于棧的，也是靠棧來(lái)遍歷的，而非統(tǒng)一版本的迭代法的中序遍歷，是靠指針來(lái)遍歷的。這二者是不同的。而統(tǒng)一版本的迭代法，前中后序都是基于棧來(lái)遍歷的。

對(duì)稱二叉樹(shù)

這道題就是后序遍歷，但是我覺(jué)得在編寫風(fēng)格上，對(duì)我來(lái)說(shuō)總感覺(jué)這不是后序遍歷，用前序遍歷的邏輯就寫出來(lái)了，似乎我還沒(méi)有完全掌握這道題。
遞歸法：

class Solution:def isSymmetric(self, root: Optional[TreeNode]) -> bool:if root == None :return Truereturn self.digui(root.left,root.right)def digui(self,left,right):if left == None and right != None :return Falseelif left != None and right == None :return Falseelif left == None and right == None :return Trueelse :if left.val != right.val :return Falseelse :flag1 = self.digui(left.left,right.right)flag2 = self.digui(left.right,right.left)return flag1 and flag2

迭代法：沒(méi)寫出來(lái)，困惑點(diǎn)在于：在判斷時(shí)，需要考慮空節(jié)點(diǎn)，但是迭代法的空節(jié)點(diǎn)，應(yīng)該不能入棧的？
使用隊(duì)列：

import collections
class Solution:def isSymmetric(self, root: TreeNode) -> bool:if not root:return Truequeue = collections.deque()queue.append(root.left) #將左子樹(shù)頭結(jié)點(diǎn)加入隊(duì)列queue.append(root.right) #將右子樹(shù)頭結(jié)點(diǎn)加入隊(duì)列while queue: #接下來(lái)就要判斷這這兩個(gè)樹(shù)是否相互翻轉(zhuǎn)leftNode = queue.popleft()rightNode = queue.popleft()if not leftNode and not rightNode: #左節(jié)點(diǎn)為空、右節(jié)點(diǎn)為空，此時(shí)說(shuō)明是對(duì)稱的continue#左右一個(gè)節(jié)點(diǎn)不為空，或者都不為空但數(shù)值不相同，返回falseif not leftNode or not rightNode or leftNode.val != rightNode.val:return Falsequeue.append(leftNode.left) #加入左節(jié)點(diǎn)左孩子queue.append(rightNode.right) #加入右節(jié)點(diǎn)右孩子queue.append(leftNode.right) #加入左節(jié)點(diǎn)右孩子queue.append(rightNode.left) #加入右節(jié)點(diǎn)左孩子return True

使用棧：

class Solution:def isSymmetric(self, root: TreeNode) -> bool:if not root:return Truest = [] #這里改成了棧st.append(root.left)st.append(root.right)while st:rightNode = st.pop()leftNode = st.pop()if not leftNode and not rightNode:continueif not leftNode or not rightNode or leftNode.val != rightNode.val:return Falsest.append(leftNode.left)st.append(rightNode.right)st.append(leftNode.right)st.append(rightNode.left)return True

層次遍歷：

class Solution:def isSymmetric(self, root: TreeNode) -> bool:if not root:return Truequeue = collections.deque([root.left, root.right])while queue:level_size = len(queue)if level_size % 2 != 0:return Falselevel_vals = []for i in range(level_size):node = queue.popleft()if node:level_vals.append(node.val)queue.append(node.left)queue.append(node.right)# 注意層次遍歷這里，空節(jié)點(diǎn)也要入棧的，這樣才能比較else:level_vals.append(None)if level_vals != level_vals[::-1]:return Falsereturn True

經(jīng)過(guò)上一題，學(xué)會(huì)了如何處理，在迭代法中要處理空節(jié)點(diǎn)的情況。統(tǒng)一風(fēng)格的迭代法中，因?yàn)橐每展?jié)點(diǎn)來(lái)標(biāo)記要處理的中間節(jié)點(diǎn)，就不能再讓空節(jié)點(diǎn)入棧了。中序迭代遍歷也不行，因?yàn)橹行虻?#xff0c;是需要指針來(lái)指示當(dāng)前位置的，所以也要求空節(jié)點(diǎn)不入棧。

前序遍歷：

class Solution:def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:if root == None :return []stack = [root]res = []while stack :node = stack.pop()if node == None :continueres.append(node.val)stack.append(node.right)stack.append(node.left)return res

層序遍歷：

class Solution:def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:if root == None :return []dq = deque()dq.append(root)res = []level = []while dq :size = len(dq)for i in range(size):node = dq.popleft()if node == None :continuelevel.append(node.val)dq.append(node.left)dq.append(node.right)if level != []:res.append(level)level = []return res

二叉樹(shù)的最大深度

根節(jié)點(diǎn)的高度等于最大深度，后序遍歷很好寫。求高度，是自底向上的，用后序遍歷。求深度，是自頂向下的，用前序遍歷。
高度求解法：

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

深度求解法：遞歸

class Solution:def maxDepth(self, root: Optional[TreeNode]) -> int:if root == None :return 0self.maxd = 0depth = 0self.digui(root,depth)return self.maxddef digui(self,root,depth):if root == None :if depth > self.maxd :self.maxd = depthreturnself.digui(root.left,depth+1)self.digui(root.right,depth+1)

迭代法，求深度

class Solution:def maxDepth(self, root: Optional[TreeNode]) -> int:if root == None :return 0stack = [(root,1)]maxd = 0while stack :(cur,depth) = stack.pop()maxd = max(maxd,depth)if cur.left :stack.append((cur.left,depth+1))if cur.right :stack.append((cur.right,depth+1))return maxd

層序遍歷法：
套用模板即可。

統(tǒng)一編寫風(fēng)格的迭代法：

class Solution:def maxDepth(self, root: Optional[TreeNode]) -> int:if root == None :return 0stack = [(root,1)]maxd = 0while stack :(cur,depth) = stack.pop()if cur :# 中stack.append((cur,depth))stack.append((None,0))# 左if cur.left :stack.append((cur.left,depth+1))# 右if cur.right :stack.append((cur.right,depth+1))# 那么在棧中的順序就是：右左中，當(dāng)然這里什么順序都不是了，因?yàn)椴恍枰厮?#xff0c;只需要記錄每次的depthelse :(cur,depth) = stack.pop()maxd = max(maxd,depth)return maxd

雖然我們之前寫過(guò)了，前中后序的迭代法代碼，但是并不代表，迭代法的代碼和遞歸中的前中后序?qū)?yīng)，非統(tǒng)一編寫風(fēng)格的迭代法只能模擬前序遍歷，后序遍歷是通過(guò)翻轉(zhuǎn)，中序遍歷是通過(guò)指針。統(tǒng)一編寫風(fēng)格的迭代法，是可以利用棧來(lái)模擬遞歸和回溯的，代碼隨想錄中也說(shuō)了，有些遞歸算法的對(duì)應(yīng)迭代法，寫起來(lái)的代碼邏輯是很難的。

非統(tǒng)一編寫風(fēng)格中，因?yàn)榭展?jié)點(diǎn)不入棧，所以無(wú)法知道，目前代碼的處理邏輯在哪個(gè)節(jié)點(diǎn)。但是統(tǒng)一風(fēng)格下，有None的存在，當(dāng)遍歷到葉子節(jié)點(diǎn)時(shí)，我們可以通過(guò)pop四次，得到左右葉子，將處理的結(jié)果append進(jìn)棧，再append一個(gè)None，我目前感覺(jué)這樣的處理邏輯應(yīng)該可行。

求二叉樹(shù)的最小深度

后序：

class Solution:def minDepth(self, root: Optional[TreeNode]) -> int:if root == None :return 0left = self.minDepth(root.left)right = self.minDepth(root.right)# 這里也可以不用left和right來(lái)判斷，可以用root.left,root.right是否為None來(lái)判斷if left == 0 and right != 0 :return 1+rightelif left != 0 and right == 0 :return 1+left# 這個(gè)判斷條件冗余了，和下面else的結(jié)果一樣elif left == 0 and right == 0 :return 1else :return 1 + min(left,right)

有點(diǎn)亂了，求最小深度，前序和迭代，不會(huì)寫

前序：

class Solution:def __init__(self):self.result = float('inf')def getDepth(self, node, depth):if node is None:returnif node.left is None and node.right is None:self.result = min(self.result, depth)if node.left:self.getDepth(node.left, depth + 1)if node.right:self.getDepth(node.right, depth + 1)def minDepth(self, root):if root is None:return 0self.getDepth(root, 1)return self.result

迭代：

class Solution:def minDepth(self, root: TreeNode) -> int:if not root:return 0depth = 0queue = collections.deque([root])while queue:depth += 1 for _ in range(len(queue)):node = queue.popleft()if not node.left and not node.right:return depthif node.left:queue.append(node.left)if node.right:queue.append(node.right)return depth

完全二叉樹(shù)的節(jié)點(diǎn)個(gè)數(shù)

利用完全二叉樹(shù)的性質(zhì)，提前判斷。但歸根結(jié)底還是后序遍歷。

如果是一般二叉樹(shù)，可以遞歸可以層序遍歷，但是想要利用完全二叉樹(shù)的性質(zhì)，只能遞歸。

class Solution:def countNodes(self, root: Optional[TreeNode]) -> int:if root == None :return 0if root.left == None and root.right == None :return 1return self.count_fun(root)def count_fun(self,root):if root == None :return 0cleft = 0cright = 0head1 = roothead2 = rootwhile head1.left :head1 = head1.leftcleft += 1while head2.right :head2 = head2.rightcright += 1if cleft == cright :number = pow(2,cleft+1)-1return numberelse :return 1 + self.count_fun(root.left) + self.count_fun(root.right)

平衡二叉樹(shù)

一開(kāi)始是想就用題目給的 isBalanced 函數(shù)，一個(gè)函數(shù)解決問(wèn)題，但是發(fā)現(xiàn)要從葉子節(jié)點(diǎn)計(jì)算高度，所以還得兩個(gè)函數(shù)。

在一個(gè)就是本題，別想著整個(gè)在迭代開(kāi)始前的判斷剪枝，其實(shí)省不了多少空間，還可能導(dǎo)致返回值異常的bug。

class Solution:def isBalanced(self, root: Optional[TreeNode]) -> bool:if root == None :return Trueself.res = Trueself.compute(root)return self.resdef compute(self,root):if root == None :return 0left = self.compute(root.left)right = self.compute(root.right)if abs(left-right) > 1 :             self.res = Falsereturn 1 + max(left,right)

求深度需要前序遍歷，從上到下去查；求高度需要后序遍歷，從下到上去計(jì)算。

這道題真正想剪枝，應(yīng)該引入一個(gè)不可能的值，作為判斷條件。

class Solution:def isBalanced(self, root: Optional[TreeNode]) -> bool:if root == None :return Trueself.res = Trueself.compute(root)return self.resdef compute(self,root):if root == None :return 0left = self.compute(root.left)if left == -1 :return -1right = self.compute(root.right)if right == -1 :return -1if abs(left-right) > 1 :             self.res = Falseresult = -1else :result = 1 + max(left,right)return result

本題的迭代法太麻煩，要先搞一個(gè)函數(shù)，專門計(jì)算深度，在搞另一個(gè)函數(shù)，從前序開(kāi)始，遍歷每一個(gè)節(jié)點(diǎn)，去判斷左右子樹(shù)，太復(fù)雜，本題的迭代法不做學(xué)習(xí)。

二叉樹(shù)的所有路徑

本題我采用了字符串作為承載路徑的數(shù)據(jù)結(jié)構(gòu)，之前我一直習(xí)慣用的是列表，可以放心大膽的 append 和 pop ， 用字符串的話，就要想好需不需要回溯，做隱式回溯的話，處理邏輯應(yīng)該放在哪里。

本題是前序遍歷。

class Solution:def binaryTreePaths(self, root: Optional[TreeNode]) -> List[str]:if root == None :return Noneself.res = []ss = ''self.find_allroad(root,ss)return self.resdef find_allroad(self,root,ss):if root == None :return if root.left == None and root.right == None :ss = ss + str(root.val)self.res.append(ss)self.find_allroad(root.left,ss + str(root.val) + '->')self.find_allroad(root.right,ss + str(root.val) + '->')

本題的迭代法，在編寫感覺(jué)上，與遞歸稍有不同，關(guān)鍵點(diǎn)在于搞清楚，增加路徑的邏輯應(yīng)該放在哪里，以及遇到葉子節(jié)點(diǎn)的處理邏輯，是否需要加入最后一個(gè)節(jié)點(diǎn)的數(shù)值？迭代法因?yàn)樵诔跏蓟瘯r(shí)，要有根節(jié)點(diǎn)，所以在加入路徑的邏輯上，與迭代法不同，要注意體會(huì)。

想不明白的時(shí)候，就自己模擬試試。

class Solution:def binaryTreePaths(self, root: Optional[TreeNode]) -> List[str]:if root == None :return Nonest = [root]path = [str(root.val)]res = []while st :node = st.pop()ss = path.pop()if node.left == None and node.right == None :res.append(ss)if node.right :st.append(node.right)path.append(ss+'->'+str(node.right.val))if node.left :st.append(node.left)path.append(ss+'->'+str(node.left.val))return res

迭代法，模擬前中后序就用棧，適合層序遍歷就用隊(duì)列。

左葉子之和

感覺(jué)自己寫的這個(gè)代碼，邏輯不是很清晰。但是代碼隨想錄的解答也是這樣寫的，如果當(dāng)前是左葉子，就覆蓋之前計(jì)算的值（這個(gè)值其實(shí)就是0），但是 if 判斷又不能放在遞歸函數(shù)前面，那樣會(huì)將正確的值覆蓋。

class Solution:def sumOfLeftLeaves(self, root: Optional[TreeNode]) -> int:if root == None :return 0left = self.sumOfLeftLeaves(root.left)right = self.sumOfLeftLeaves(root.right)if root.left != None and root.left.left == None and root.left.right == None :left = root.left.valreturn left + right

錯(cuò)誤的 if 位置，錯(cuò)誤的代碼：

class Solution:def sumOfLeftLeaves(self, root: Optional[TreeNode]) -> int:if root == None :return 0if root.left != None and root.left.left == None and root.left.right == None :left = root.left.valleft = self.sumOfLeftLeaves(root.left)right = self.sumOfLeftLeaves(root.right)return left + right

迭代法：前序遍歷，統(tǒng)計(jì)每一個(gè)左葉子就好了。

class Solution:def sumOfLeftLeaves(self, root: Optional[TreeNode]) -> int:if root == None :return 0st = [root]res = 0while st :node = st.pop()if node.left != None and node.left.left == None and node.left.right == None :res += node.left.valif node.left :st.append(node.left)if node.right :st.append(node.right)return res

樹(shù)左下角的值

本題使用層序遍歷，思路非常簡(jiǎn)單，是層序遍歷的模板題，這里我使用遞歸。

遞歸，要使用前序遍歷，這樣才能優(yōu)先左邊搜。

class Solution:def findBottomLeftValue(self, root: Optional[TreeNode]) -> int:self.maxdepth = 0# 如果depth初值給0的話，因?yàn)橐婚_(kāi)始會(huì)等于maxdepth，就要單獨(dú)判斷，二叉樹(shù)只有一個(gè)# 根節(jié)點(diǎn)的情況了，如果給1的話，就不需要單獨(dú)判斷depth = 1self.value = 0self.find_left(root,depth)return self.valuedef find_left(self,root,depth):if root == None :returnif root.left == None and root.right == None :# 本題的關(guān)鍵就在于這一句，必須是嚴(yán)格大于if depth > self.maxdepth :self.maxdepth = depthself.value = root.valself.find_left(root.left,depth+1)self.find_left(root.right,depth+1)

路徑總和

第一次自己嘗試編寫，代碼隨想錄風(fēng)格的，利用設(shè)置返回值，找到就返回的遞歸代碼。

需要注意的還是那一點(diǎn)：理清處理邏輯，遞歸函數(shù)怎么寫，需不需要回溯，需要回溯，想寫成隱式的怎么寫，顯式的怎么寫，在收獲結(jié)果的時(shí)候，處理邏輯怎么寫，終止條件怎么寫。

class Solution:def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:if root == None :return False# 注意處理邏輯，一開(kāi)始這里最后一個(gè)條件我寫的是：targetSum == 0 ，一直錯(cuò)誤# 后來(lái)才發(fā)現(xiàn)，我沒(méi)有去處理最后一個(gè)節(jié)點(diǎn)！if root.left == None and root.right == None and targetSum == root.val :return Trueif self.hasPathSum(root.left,targetSum-root.val) :return Trueif self.hasPathSum(root.right,targetSum-root.val) :return Truereturn False

迭代法：

class Solution:def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:if root == None :return Falsest = [root]value = [targetSum]while st :node = st.pop()t = value.pop()if node.left == None and node.right == None and t == node.val :return Trueif node.left :st.append(node.left)value.append(t-node.val)if node.right :st.append(node.right)value.append(t-node.val)return False

路徑總和II

class Solution:def pathSum(self, root: Optional[TreeNode], targetSum: int) -> List[List[int]]:if root == None :return []self.res = []path = []self.find_all_road(root,path,targetSum)return self.resdef find_all_road(self,root,path,targetSum):if root == None :returnif root.left == None and root.right == None and targetSum == root.val :path.append(root.val)self.res.append(path.copy())path.pop()path.append(root.val)self.find_all_road(root.left,path,targetSum-root.val)self.find_all_road(root.right,path,targetSum-root.val)path.pop()

用迭代法記錄所有路徑是很繁瑣的，這種題不適合迭代法，一定要體會(huì)其中區(qū)別！問(wèn)“有沒(méi)有？”，迭代法可以；“找出所有可能？”迭代法不行。

遞歸函數(shù)，什么時(shí)候需要返回值，什么時(shí)候不需要？

如果需要搜索整棵二叉樹(shù)且不用處理遞歸返回值，遞歸函數(shù)就不要返回值。（這種情況就是本文下半部分介紹的113.路徑總和ii）

如果需要搜索整棵二叉樹(shù)且需要處理遞歸返回值，遞歸函數(shù)就需要返回值。 （這種情況我們?cè)?36. 二叉樹(shù)的最近公共祖先 (opens new window)中介紹）

如果要搜索其中一條符合條件的路徑，那么遞歸一定需要返回值，因?yàn)橛龅椒蠗l件的路徑了就要及時(shí)返回。（本題的情況）

前面兩道，路徑總和的題，可以在子節(jié)點(diǎn)判斷后，再加一個(gè)判斷做剪枝

		if root == None :returnif root.left == None and root.right == None and targetSum == root.val :path.append(root.val)self.res.append(path.copy())path.pop()if root.left == None and root.right == None :return

但是一定要注意順序，要放在判斷當(dāng)前葉子節(jié)點(diǎn)不符合要求之后。

前面兩題，我寫的和代碼隨想錄寫的細(xì)節(jié)有些不同，我是從空列表開(kāi)始遞歸，卡哥是先讓根節(jié)點(diǎn)入棧了，這一個(gè)差異，就導(dǎo)致代碼編寫風(fēng)格差異一看上去還挺大。

中序后序建立二叉樹(shù)，前序中序建立二叉樹(shù)，這兩題只要想清楚，區(qū)間的左右邊界就可以了，過(guò)。

最大二叉樹(shù)，同上一題，都是構(gòu)造的題目

合并二叉樹(shù)

class Solution:def mergeTrees(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> Optional[TreeNode]:if root1 == None and root2 == None :return Noneelif root1 == None :return root2elif root2 == None :return root1else :root1.val += root2.valroot1.left = self.mergeTrees(root1.left,root2.left)root1.right = self.mergeTrees(root1.right,root2.right)return root1

構(gòu)造樹(shù)，一般采用的是前序遍歷，因?yàn)橄葮?gòu)造中間節(jié)點(diǎn)，然后遞歸構(gòu)造左子樹(shù)和右子樹(shù)。

迭代法：代碼隨想錄給的是用對(duì)隊(duì)列，但是并不是層序遍歷的模板！用棧作為容器一樣可以！這里我是用的棧。

class Solution:def mergeTrees(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> Optional[TreeNode]:if root1 == None :return root2if root2 == None :return root1head = root1st = [root1,root2]while st :# 因?yàn)橛玫氖菞?#xff0c;后進(jìn)先出，這里順序要注意，是反的root2 = st.pop()root1 = st.pop()root1.val += root2.val# 在四個(gè)有效的判斷中，順序很重要，要先判定左右是否都不空# 因?yàn)楫?dāng)root有空時(shí)，會(huì)存在給root1的賦值操作，這時(shí)候再判斷，本來(lái)一空一不空，# 現(xiàn)在變成都不空了，出現(xiàn)錯(cuò)誤！if root1.left != None and root2.left != None :st.append(root1.left)st.append(root2.left)if root1.right != None and root2.right != None :st.append(root1.right)st.append(root2.right)if root1.left == None and root2.left != None :root1.left = root2.leftif root1.left != None and root2.left == None : # 可不寫pass if root1.right == None and root2.right != None :root1.right = root2.rightif root1.right != None and root2.right == None : # 可不寫pass# 還有，root1和root2的左孩子均為空，root1和root2的右孩子均為空# 這兩種情況，也可以不寫return head

二叉搜索樹(shù)中的搜索

class Solution:def searchBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:if root == None :return Noneif root.val == val :return rootif root.val > val :res = self.searchBST(root.left,val)if res :return reselse :res = self.searchBST(root.right,val)if res :return resreturn None

精簡(jiǎn)版本：不管返回值是不是None ， 直接返回就行！

class Solution:def searchBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:if root == None :return Noneif root.val == val :return rootif root.val > val :return self.searchBST(root.left,val)else :return self.searchBST(root.right,val)

二叉搜索樹(shù)，因?yàn)槠浣Y(jié)構(gòu)特殊性的存在，不需要回溯操作，所以不需要?；蜿?duì)列來(lái)模擬遞歸。直接循環(huán)！

class Solution:def searchBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:if root == None :return Nonewhile root != None :if root.val == val :return rootif root.val > val :root = root.leftelse :root = root.rightreturn None

驗(yàn)證二叉搜索樹(shù)(重要！重要！重要！因?yàn)槲乙恢辈粫?huì))

這道題我竟然還是不會(huì)！

現(xiàn)在能想到，避開(kāi)陷阱，不是僅僅比較左右孩子就可以的！

但是，依然忘了迭代法怎么編寫！

遞歸法就是先中序遍歷得到數(shù)組，再遍歷數(shù)組。

class Solution:def __init__(self):self.vec = []def traversal(self, root):if root is None:returnself.traversal(root.left)self.vec.append(root.val)  # 將二叉搜索樹(shù)轉(zhuǎn)換為有序數(shù)組self.traversal(root.right)def isValidBST(self, root):self.vec = []  # 清空數(shù)組self.traversal(root)for i in range(1, len(self.vec)):# 注意要小于等于，搜索樹(shù)里不能有相同元素if self.vec[i] <= self.vec[i - 1]:return Falsereturn True

這里用遞歸法的一個(gè)技巧在于，聲明一個(gè)全局變量節(jié)點(diǎn)。

class Solution:def __init__(self):self.pre = None  # 用來(lái)記錄前一個(gè)節(jié)點(diǎn)def isValidBST(self, root):if root is None:return Trueleft = self.isValidBST(root.left)if self.pre is not None and self.pre.val >= root.val:return Falseself.pre = root  # 記錄前一個(gè)節(jié)點(diǎn)right = self.isValidBST(root.right)return left and right

迭代法：

class Solution:def isValidBST(self, root):stack = []cur = rootpre = None  # 記錄前一個(gè)節(jié)點(diǎn)while cur is not None or len(stack) > 0:if cur is not None:stack.append(cur)cur = cur.left  # 左else:cur = stack.pop()  # 中if pre is not None and cur.val <= pre.val:return Falsepre = cur  # 保存前一個(gè)訪問(wèn)的結(jié)點(diǎn)cur = cur.right  # 右return True

看到二叉搜索樹(shù)就要想到中序遍歷，中序遍歷得到的數(shù)組是遞增的。

二叉搜索樹(shù)的最小絕對(duì)差

代碼邏輯和上一題完全相同。

class Solution:def __init__(self):self.pre = Noneself.minabs = infdef getMinimumDifference(self, root: Optional[TreeNode]) -> int:if root == None :return 0self.getMinimumDifference(root.left)if self.pre != None :self.minabs = min(self.minabs,root.val-self.pre.val)self.pre = rootself.getMinimumDifference(root.right)return self.minabs

class Solution:def getMinimumDifference(self, root: Optional[TreeNode]) -> int:if root == None :return 0res = infpre = Nonecur = rootst = []while st or cur :if cur :st.append(cur)cur = cur.leftelse :cur = st.pop()if pre != None :res = min(res,cur.val-pre.val)pre = curcur = cur.rightreturn res

二叉搜索樹(shù)中的眾數(shù)

怎么bug一直調(diào)不好了？這題有很多細(xì)節(jié)我沒(méi)注意到，下面的是錯(cuò)誤的代碼

class Solution:def findMode(self, root: Optional[TreeNode]) -> List[int]:self.maxcount = 1self.res = []self.pre = Noneself.count = 1self.findall(root)return self.resdef findall(self,root):if root == None :return self.findall(root.left)if self.pre :if self.pre.val == root.val :self.count += 1else :count = 1if self.count > self.maxcount :self.res.clear()self.res.append(root.val)self.maxcount = self.countelif self.count == self.maxcount :self.res.append(root.val)self.pre = rootself.findall(root.right)

上述代碼的致命錯(cuò)誤，大致如下：首先是初始化上的錯(cuò)誤，兩個(gè)計(jì)數(shù)器必須全部置0，另外，讓根節(jié)點(diǎn)進(jìn)去結(jié)果列表，這是毫無(wú)道理的！第二點(diǎn)就是沒(méi)有處理好第一個(gè)節(jié)點(diǎn)（最左下的節(jié)點(diǎn)），當(dāng) pre 是 None 時(shí)，我們應(yīng)該將 count 賦值為 1 ，這樣最左下的節(jié)點(diǎn)就可能作為結(jié)果。第三點(diǎn)，對(duì)于當(dāng)前節(jié)點(diǎn)是否是空節(jié)點(diǎn)的判斷，只能決定，當(dāng)前的 count 是多少，而結(jié)果處理邏輯，肯定是要放在 if 判斷之外的，不然也同樣會(huì)漏掉，最左下節(jié)點(diǎn)作為結(jié)果的情況。

正確代碼：

class Solution:def findMode(self, root: Optional[TreeNode]) -> List[int]:self.maxcount = 0self.res = []self.pre = Noneself.count = 0self.findall(root)return self.resdef findall(self,root):if root == None :return self.findall(root.left)if self.pre :if self.pre.val == root.val :self.count += 1else :self.count = 1else :self.count = 1if self.count > self.maxcount :self.res.clear()self.res.append(root.val)self.maxcount = self.countelif self.count == self.maxcount :self.res.append(root.val)self.pre = rootself.findall(root.right)

迭代法，就是中序遍歷，只要理清本題的，眾數(shù)處理邏輯就好，和遞歸的邏輯是一樣的

class Solution:def findMode(self, root: Optional[TreeNode]) -> List[int]:count = 0maxcount = 0pre = Nonecur = rootst = []res = []while st or cur :if cur :st.append(cur)cur = cur.leftelse :cur = st.pop()if pre :if pre.val == cur.val :count += 1else :count = 1else :count = 1pre = curif count > maxcount :res.clear()res.append(cur.val)maxcount = countelif count == maxcount :res.append(cur.val)cur = cur.rightreturn res

如果本題不是二叉搜索樹(shù)，而是一般二叉樹(shù)，就要利用字典了

from collections import defaultdictclass Solution:def searchBST(self, cur, freq_map):if cur is None:returnfreq_map[cur.val] += 1  # 統(tǒng)計(jì)元素頻率self.searchBST(cur.left, freq_map)self.searchBST(cur.right, freq_map)def findMode(self, root):freq_map = defaultdict(int)  # key:元素，value:出現(xiàn)頻率result = []if root is None:return resultself.searchBST(root, freq_map)max_freq = max(freq_map.values())for key, freq in freq_map.items():if freq == max_freq:result.append(key)return result

二叉樹(shù)的最近公共祖先

首先明確用后序遍歷，其次要明白，為什么當(dāng)左右只有一個(gè)有值時(shí)，返回這個(gè)值就可以了。

class Solution:def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':if root == None :return Noneif root == p or root == q :return rootleft = self.lowestCommonAncestor(root.left,p,q)right = self.lowestCommonAncestor(root.right,p,q)if left != None and right != None :return rootelif left != None and right == None :return leftelif left == None and right != None :return rightelse :return None

本題沒(méi)有迭代法，本題的講解寫的很好，可以多讀讀。
最近公共祖先

二叉搜索樹(shù)的最近公共祖先

又沒(méi)寫出來(lái)，錯(cuò)誤代碼如下。受上一題影響，總想在上一題的基礎(chǔ)上稍作改動(dòng)，但是發(fā)現(xiàn)，在二叉搜索樹(shù)中，同時(shí)匹配兩個(gè)值是不現(xiàn)實(shí)的，邏輯會(huì)非常混亂。

class Solution:def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':if root == None :return Noneif root == p or root == q :return rootif root.val > p.val and root.val > q.val:return self.lowestCommonAncestor(root.left,p,q)elif root.val < p.val and root.val < q.val:return self.lowestCommonAncestor(root.right,p,q)else :left = 

這道題，因?yàn)橛行驑?shù)的存在，思路和上一題完全不一樣了！本題的核心在于利用二叉搜索樹(shù)的性質(zhì)。需要理解的是，按照如下規(guī)則找到的節(jié)點(diǎn)，一定是最近的公共祖先，因?yàn)橐坏┫蛳逻M(jìn)入左右孩子，必然會(huì)丟失掉 p q 中的一個(gè)。

class Solution:def traversal(self, cur, p, q):if cur is None:return cur# 中if cur.val > p.val and cur.val > q.val:           # 左left = self.traversal(cur.left, p, q)if left is not None:return leftif cur.val < p.val and cur.val < q.val:           # 右right = self.traversal(cur.right, p, q)if right is not None:return rightreturn curdef lowestCommonAncestor(self, root, p, q):return self.traversal(root, p, q)

既然本題已經(jīng)無(wú)所謂遍歷順序，變成了一道尋找二叉搜索樹(shù)的節(jié)點(diǎn)的題目，迭代法自然可行，且簡(jiǎn)便了。

class Solution:def lowestCommonAncestor(self, root, p, q):while root:if root.val > p.val and root.val > q.val:root = root.leftelif root.val < p.val and root.val < q.val:root = root.rightelse:return rootreturn None

二叉搜索樹(shù)中的插入操作

本題要注意的是，一定要寫遞歸函數(shù)返回值，利用返回值去修改二叉樹(shù)，如果沒(méi)有修改，返回值就是原本樹(shù)的自身。

另外，本題要理解，明確只往空節(jié)點(diǎn)插入就可以了，不要想著更改樹(shù)的結(jié)構(gòu)。

class Solution:def insertIntoBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:root = self.insert(root,val)return rootdef insert(self,root,val):if root == None :node = TreeNode(val)           return nodeif root.val > val :root.left = self.insert(root.left,val)else :root.right = self.insert(root.right,val)return root

其實(shí)不需要額外定義一個(gè)函數(shù)。

class Solution:def insertIntoBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:if root == None :node = TreeNode(val)           return nodeif root.val > val :root.left = self.insertIntoBST(root.left,val)else :root.right = self.insertIntoBST(root.right,val)return root

刪除二叉搜索樹(shù)中的節(jié)點(diǎn)

這道題寫下來(lái)還是蠻難的，而且我感覺(jué)我現(xiàn)在的邏輯也沒(méi)有很清晰，加了不少 if 判斷。我主要的思路就是，刪除當(dāng)前節(jié)點(diǎn)后，直接用當(dāng)前節(jié)點(diǎn)的左孩子頂上來(lái)，然后把當(dāng)前節(jié)點(diǎn)的右子樹(shù)，加到左孩子的最右。這樣就滿足二叉搜索樹(shù)的性質(zhì)。但是還要處理很多特殊情況，這也是我這么多 if 的由來(lái)，比如我取了當(dāng)前節(jié)點(diǎn)的左右孩子，那么自然就要考慮，如果是空怎么辦？都是空？一個(gè)是空？情況都要考慮清楚。

只要取了節(jié)點(diǎn)的左右孩子，還想取它的value，就要想到，判斷是否是None?？纯创a隨想錄的解答吧

我的代碼：目標(biāo)刪除節(jié)點(diǎn)的右孩子，往目標(biāo)刪除節(jié)點(diǎn)的左孩子的最右去接

class Solution:def deleteNode(self, root: Optional[TreeNode], key: int) -> Optional[TreeNode]:if root == None :return Noneif root.val < key :root.right = self.deleteNode(root.right,key)elif root.val > key :root.left = self.deleteNode(root.left,key)else :node = root.left        pre = root.rightif node == None and pre == None: # 左右均為空return Noneelif node == None : # 左為空return pre# 這里我覺(jué)得是，我是讓右孩子向右接，所以 pre 為空，無(wú)所謂else :while node.right :node = node.rightnode.right = prereturn root.leftreturn root

刪除二叉搜索樹(shù)中的節(jié)點(diǎn)

卡哥給出的，普通樹(shù)的刪除方法，以及迭代法，都先不做學(xué)習(xí)了，先掌握最基本的遞歸法。

根據(jù)卡哥給的思路，對(duì)上面自己的代碼進(jìn)行了小修改，思路是：目標(biāo)刪除節(jié)點(diǎn)的左孩子，往目標(biāo)刪除節(jié)點(diǎn)的右孩子的最左去接。

class Solution:def deleteNode(self, root: Optional[TreeNode], key: int) -> Optional[TreeNode]:if root == None :return Noneif root.val < key :root.right = self.deleteNode(root.right,key)elif root.val > key :root.left = self.deleteNode(root.left,key)else :node = root.left        pre = root.rightif node == None and pre == None: # 左右都為空return Noneelif node == None : # 左為空return preelif pre == None : # 右為空return nodeelse :while pre.left :pre = pre.left      pre.left = nodereturn root.rightreturn root

本題對(duì)于第五步，刪除拼接的情況，本來(lái)就有兩種選擇，上面我都提到了，左接右，右接左。

代碼隨想錄的代碼：

class Solution:def deleteNode(self, root, key):if root is None:return rootif root.val == key:if root.left is None and root.right is None:return Noneelif root.left is None:return root.rightelif root.right is None:return root.leftelse:cur = root.rightwhile cur.left is not None:cur = cur.leftcur.left = root.leftreturn root.rightif root.val > key:root.left = self.deleteNode(root.left, key)if root.val < key:root.right = self.deleteNode(root.right, key)return root

修剪二叉搜索樹(shù)

不會(huì)，理不清處理邏輯。

自己寫的錯(cuò)誤代碼：

class Solution:def trimBST(self, root: Optional[TreeNode], low: int, high: int) -> Optional[TreeNode]:if root == None :return Noneif root.val >= low and root.val <= high :root.left = self.trimBST(root.left,low,high)root.right = self.trimBST(root.right,low,high)return root   elif root.val < low :head = root.rightif head == None :return Nonehead.left = self.trimBST(head.left,low,high)head.right = self.trimBST(head.right,low,high)return headelif root.val > high :head = root.leftif head == None :return Nonehead.left = self.trimBST(head.left,low,high)head.right = self.trimBST(head.right,low,high)return head

看看代碼隨想錄的解答。這是一個(gè)思維轉(zhuǎn)變的問(wèn)題，好好理解。

修剪二叉搜索樹(shù)

class Solution:def trimBST(self, root: TreeNode, low: int, high: int) -> TreeNode:if root is None:return Noneif root.val < low:# 尋找符合區(qū)間 [low, high] 的節(jié)點(diǎn)return self.trimBST(root.right, low, high)if root.val > high:# 尋找符合區(qū)間 [low, high] 的節(jié)點(diǎn)return self.trimBST(root.left, low, high)root.left = self.trimBST(root.left, low, high)  # root.left 接入符合條件的左孩子root.right = self.trimBST(root.right, low, high)  # root.right 接入符合條件的右孩子return root

這道題非常非常重要。迭代法先不做學(xué)習(xí)了、

將有序數(shù)組轉(zhuǎn)換為二叉搜索樹(shù)

取數(shù)組中間數(shù)值，遞歸構(gòu)造即可。

把二叉搜索樹(shù)轉(zhuǎn)換為累加樹(shù)

之前做過(guò)類似的題。

class Solution:def __init__(self):self.last = Nonedef convertBST(self, root: Optional[TreeNode]) -> Optional[TreeNode]:if root == None :return Noneroot.right = self.convertBST(root.right)if self.last :root.val += self.last.valself.last = rootroot.left = self.convertBST(root.left)return root

迭代法：

class Solution:def convertBST(self, root: Optional[TreeNode]) -> Optional[TreeNode]:if root == None :return Nonest = []cur = rootlast = Nonewhile st or cur :if cur :st.append(cur)cur = cur.rightelse :cur = st.pop()if last :cur.val += last.vallast = curcur = cur.leftreturn root