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

二叉樹章節(jié)

二叉樹章節(jié)，做不出來的題基本上都有一個共性，對二叉樹的數據結構特性不熟悉，從而沒有編寫思路，或者在判斷條件上產生疏漏。

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

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

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

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

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

深度優(yōu)先遍歷的三種方法中，后序遍歷是應用最多的，因為很多時候，我們都需要去收集，左右子樹的信息，來決定當前節(jié)點的方式，或者說，需要將某些信息，一層一層地返回到根節(jié)點，這時候都需要后序遍歷。中序遍歷，和二叉搜索樹，嚴格綁定。前序遍歷需要的場景，一般都有比較明顯的特征，可以意識到。

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

二叉樹的節(jié)點定義：

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

遞歸三部曲

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

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

兩個版本代碼的對比，一個帶空節(jié)點判斷，一個不帶。

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)

二叉樹的迭代遍歷(一定要學會)

前序遍歷：

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é)點不入棧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é)點不入棧if node.left:stack.append(node.left)if node.right:stack.append(node.right)# 代碼編寫順序是，中左右，但是因為使用的是棧，那么在res數組中的順序是，中右左，倒序，左右中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é)點不入棧if cur :stack.append(cur)cur = cur.leftelse :cur = stack.pop()res.append(cur.val)cur = cur.rightreturn res

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

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

以中序遍歷為例：因為是迭代法，使用的是棧作為數據結構，在代碼中的編寫順序，和在結果集中的保存順序，是不一樣的。代碼編寫是，右中左，結果集中就是，左中右

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 :# 當node不是空節(jié)點時的操作，是關鍵# 要根據遍歷順序重新調整元素順序# 因為是使用堆棧，所以要從下向上看，左中右if node.right :  # 右stack.append(node.right)stack.append(node) # 中stack.append(None)if node.left : # 左stack.append(node.left)return res

二叉樹的層序遍歷

層序遍歷是有標準寫法的。代碼隨想錄中列出的，與層序遍歷相關的10道題，都是稍微修改就可以做出來的。

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. 填充每個節(jié)點的下一個右側節(jié)點指針 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.二叉樹的最大深度

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.二叉樹的最小深度

需要注意的是，只有當左右孩子都為空的時候，才說明遍歷的最低點了。如果其中一個孩子為空則不是最低點.

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

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

226.翻轉二叉樹，通過本題，希望學會，如何將遞歸方法中的邏輯，寫在相對應的迭代法中

本題用什么遍歷順序？

對于使用基于遞歸的方法來說：前序，后序，層序，都可以。唯獨中序不行。這個自己畫畫圖就可以知道。

對于使用迭代的方法來說：同遞歸。（這里的迭代，指的是，不加入None的迭代法）

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

遞歸代碼，前序遍歷：

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)一迭代風格的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é)點處理邏輯}}return root;}
};

為什么這個中序就是可以的呢，因為這是用棧來遍歷，而不是靠指針來遍歷，避免了遞歸法中翻轉了兩次的情況。

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

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

對稱二叉樹

這道題就是后序遍歷，但是我覺得在編寫風格上，對我來說總感覺這不是后序遍歷，用前序遍歷的邏輯就寫出來了，似乎我還沒有完全掌握這道題。
遞歸法：

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

迭代法：沒寫出來，困惑點在于：在判斷時，需要考慮空節(jié)點，但是迭代法的空節(jié)點，應該不能入棧的？
使用隊列：

import collections
class Solution:def isSymmetric(self, root: TreeNode) -> bool:if not root:return Truequeue = collections.deque()queue.append(root.left) #將左子樹頭結點加入隊列queue.append(root.right) #將右子樹頭結點加入隊列while queue: #接下來就要判斷這這兩個樹是否相互翻轉leftNode = queue.popleft()rightNode = queue.popleft()if not leftNode and not rightNode: #左節(jié)點為空、右節(jié)點為空，此時說明是對稱的continue#左右一個節(jié)點不為空，或者都不為空但數值不相同，返回falseif not leftNode or not rightNode or leftNode.val != rightNode.val:return Falsequeue.append(leftNode.left) #加入左節(jié)點左孩子queue.append(rightNode.right) #加入右節(jié)點右孩子queue.append(leftNode.right) #加入左節(jié)點右孩子queue.append(rightNode.left) #加入右節(jié)點左孩子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é)點也要入棧的，這樣才能比較else:level_vals.append(None)if level_vals != level_vals[::-1]:return Falsereturn True

經過上一題，學會了如何處理，在迭代法中要處理空節(jié)點的情況。統(tǒng)一風格的迭代法中，因為要用空節(jié)點來標記要處理的中間節(jié)點，就不能再讓空節(jié)點入棧了。中序迭代遍歷也不行，因為中序迭代法，是需要指針來指示當前位置的，所以也要求空節(jié)點不入棧。

前序遍歷：

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

二叉樹的最大深度

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

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)一編寫風格的迭代法：

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))# 那么在棧中的順序就是：右左中，當然這里什么順序都不是了，因為不需要回溯，只需要記錄每次的depthelse :(cur,depth) = stack.pop()maxd = max(maxd,depth)return maxd

雖然我們之前寫過了，前中后序的迭代法代碼，但是并不代表，迭代法的代碼和遞歸中的前中后序對應，非統(tǒng)一編寫風格的迭代法只能模擬前序遍歷，后序遍歷是通過翻轉，中序遍歷是通過指針。統(tǒng)一編寫風格的迭代法，是可以利用棧來模擬遞歸和回溯的，代碼隨想錄中也說了，有些遞歸算法的對應迭代法，寫起來的代碼邏輯是很難的。

非統(tǒng)一編寫風格中，因為空節(jié)點不入棧，所以無法知道，目前代碼的處理邏輯在哪個節(jié)點。但是統(tǒng)一風格下，有None的存在，當遍歷到葉子節(jié)點時，我們可以通過pop四次，得到左右葉子，將處理的結果append進棧，再append一個None，我目前感覺這樣的處理邏輯應該可行。

求二叉樹的最小深度

后序：

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來判斷，可以用root.left,root.right是否為None來判斷if left == 0 and right != 0 :return 1+rightelif left != 0 and right == 0 :return 1+left# 這個判斷條件冗余了，和下面else的結果一樣elif left == 0 and right == 0 :return 1else :return 1 + min(left,right)

有點亂了，求最小深度，前序和迭代，不會寫

前序：

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

完全二叉樹的節(jié)點個數

利用完全二叉樹的性質，提前判斷。但歸根結底還是后序遍歷。

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

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)

平衡二叉樹

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

在一個就是本題，別想著整個在迭代開始前的判斷剪枝，其實省不了多少空間，還可能導致返回值異常的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)

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

這道題真正想剪枝，應該引入一個不可能的值，作為判斷條件。

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

本題的迭代法太麻煩，要先搞一個函數，專門計算深度，在搞另一個函數，從前序開始，遍歷每一個節(jié)點，去判斷左右子樹，太復雜，本題的迭代法不做學習。

二叉樹的所有路徑

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

本題是前序遍歷。

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) + '->')

本題的迭代法，在編寫感覺上，與遞歸稍有不同，關鍵點在于搞清楚，增加路徑的邏輯應該放在哪里，以及遇到葉子節(jié)點的處理邏輯，是否需要加入最后一個節(jié)點的數值？迭代法因為在初始化時，要有根節(jié)點，所以在加入路徑的邏輯上，與迭代法不同，要注意體會。

想不明白的時候，就自己模擬試試。

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

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

左葉子之和

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

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

錯誤的 if 位置，錯誤的代碼：

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)計每一個左葉子就好了。

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

樹左下角的值

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

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

class Solution:def findBottomLeftValue(self, root: Optional[TreeNode]) -> int:self.maxdepth = 0# 如果depth初值給0的話，因為一開始會等于maxdepth，就要單獨判斷，二叉樹只有一個# 根節(jié)點的情況了，如果給1的話，就不需要單獨判斷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 :# 本題的關鍵就在于這一句，必須是嚴格大于if depth > self.maxdepth :self.maxdepth = depthself.value = root.valself.find_left(root.left,depth+1)self.find_left(root.right,depth+1)

路徑總和

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

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

class Solution:def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:if root == None :return False# 注意處理邏輯，一開始這里最后一個條件我寫的是：targetSum == 0 ，一直錯誤# 后來才發(fā)現(xiàn)，我沒有去處理最后一個節(jié)點！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()

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

遞歸函數，什么時候需要返回值，什么時候不需要？

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

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

如果要搜索其中一條符合條件的路徑，那么遞歸一定需要返回值，因為遇到符合條件的路徑了就要及時返回。（本題的情況）

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

		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

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

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

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

最大二叉樹，同上一題，都是構造的題目

合并二叉樹

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

構造樹，一般采用的是前序遍歷，因為先構造中間節(jié)點，然后遞歸構造左子樹和右子樹。

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

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 :# 因為用的是棧，后進先出，這里順序要注意，是反的root2 = st.pop()root1 = st.pop()root1.val += root2.val# 在四個有效的判斷中，順序很重要，要先判定左右是否都不空# 因為當root有空時，會存在給root1的賦值操作，這時候再判斷，本來一空一不空，# 現(xiàn)在變成都不空了，出現(xiàn)錯誤！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

二叉搜索樹中的搜索

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

精簡版本：不管返回值是不是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)

二叉搜索樹，因為其結構特殊性的存在，不需要回溯操作，所以不需要?；蜿犃衼砟M遞歸。直接循環(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

驗證二叉搜索樹(重要！重要！重要！因為我一直不會)

這道題我竟然還是不會！

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

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

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

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

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

class Solution:def __init__(self):self.pre = None  # 用來記錄前一個節(jié)點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  # 記錄前一個節(jié)點right = self.isValidBST(root.right)return left and right

迭代法：

class Solution:def isValidBST(self, root):stack = []cur = rootpre = None  # 記錄前一個節(jié)點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  # 保存前一個訪問的結點cur = cur.right  # 右return True

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

二叉搜索樹的最小絕對差

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

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

二叉搜索樹中的眾數

怎么bug一直調不好了？這題有很多細節(jié)我沒注意到，下面的是錯誤的代碼

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)

上述代碼的致命錯誤，大致如下：首先是初始化上的錯誤，兩個計數器必須全部置0，另外，讓根節(jié)點進去結果列表，這是毫無道理的！第二點就是沒有處理好第一個節(jié)點（最左下的節(jié)點），當 pre 是 None 時，我們應該將 count 賦值為 1 ，這樣最左下的節(jié)點就可能作為結果。第三點，對于當前節(jié)點是否是空節(jié)點的判斷，只能決定，當前的 count 是多少，而結果處理邏輯，肯定是要放在 if 判斷之外的，不然也同樣會漏掉，最左下節(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)

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

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

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

from collections import defaultdictclass Solution:def searchBST(self, cur, freq_map):if cur is None:returnfreq_map[cur.val] += 1  # 統(tǒng)計元素頻率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

二叉樹的最近公共祖先

首先明確用后序遍歷，其次要明白，為什么當左右只有一個有值時，返回這個值就可以了。

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

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

二叉搜索樹的最近公共祖先

又沒寫出來，錯誤代碼如下。受上一題影響，總想在上一題的基礎上稍作改動，但是發(fā)現(xiàn)，在二叉搜索樹中，同時匹配兩個值是不現(xiàn)實的，邏輯會非?；靵y。

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 = 

這道題，因為有序樹的存在，思路和上一題完全不一樣了！本題的核心在于利用二叉搜索樹的性質。需要理解的是，按照如下規(guī)則找到的節(jié)點，一定是最近的公共祖先，因為一旦向下進入左右孩子，必然會丟失掉 p q 中的一個。

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)

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

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

二叉搜索樹中的插入操作

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

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

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

其實不需要額外定義一個函數。

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

刪除二叉搜索樹中的節(jié)點

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

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

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

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# 這里我覺得是，我是讓右孩子向右接，所以 pre 為空，無所謂else :while node.right :node = node.rightnode.right = prereturn root.leftreturn root

刪除二叉搜索樹中的節(jié)點

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

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

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

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

代碼隨想錄的代碼：

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

修剪二叉搜索樹

不會，理不清處理邏輯。

自己寫的錯誤代碼：

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

看看代碼隨想錄的解答。這是一個思維轉變的問題，好好理解。

修剪二叉搜索樹

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é)點return self.trimBST(root.right, low, high)if root.val > high:# 尋找符合區(qū)間 [low, high] 的節(jié)點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

這道題非常非常重要。迭代法先不做學習了、

將有序數組轉換為二叉搜索樹

取數組中間數值，遞歸構造即可。

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

之前做過類似的題。

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