建设建网站,萍乡网站制作公司,无组件上传网站,大专自考报名入口官网读PDF复习环节2 本博客的内容只是做一个大概的记录#xff0c;整个PDF看下来#xff0c;内容上是不如代码随想录网站上的文章全面的#xff0c;并且PDF中有些地方的描述#xff0c;是很让我疑惑的#xff0c;在困扰我很久后#xff0c;无意间发现#xff0c;其网站上的讲… 读PDF复习环节2 本博客的内容只是做一个大概的记录整个PDF看下来内容上是不如代码随想录网站上的文章全面的并且PDF中有些地方的描述是很让我疑惑的在困扰我很久后无意间发现其网站上的讲解完全符合我的思路。这次看完这些PDF后暂时一段时间内不会再看了要复习还是依靠代码随想录网站视频和我自己写的博客吧二叉树章节递归三部曲判断了递归中不会有空节点就可以不写返回条件以前序遍历为例二叉树的迭代遍历(一定要学会)前中后序遍历的统一迭代方法二叉树的层序遍历117. 填充每个节点的下一个右侧节点指针 II104.二叉树的最大深度111.二叉树的最小深度上面求最大深度和最小深度的题目我们后面还会遇到可以发现其实递归也不一定比迭代法好用只不过能不能想的到使用层序遍历就是需要修炼的了。226.翻转二叉树通过本题希望学会如何将递归方法中的逻辑写在相对应的迭代法中只要是能编写出相应迭代法的递归法在时间复杂度上二者差不多在空间复杂度上迭代法要优于递归。因为递归需要系统堆栈存储参数返回值等信息。通过上一题我们要意识到非统一版本的迭代法前序和后序都是基于栈的也是靠栈来遍历的而非统一版本的迭代法的中序遍历是靠指针来遍历的。这二者是不同的。而统一版本的迭代法前中后序都是基于栈来遍历的。对称二叉树经过上一题学会了如何处理在迭代法中要处理空节点的情况。统一风格的迭代法中因为要用空节点来标记要处理的中间节点就不能再让空节点入栈了。中序迭代遍历也不行因为中序迭代法是需要指针来指示当前位置的所以也要求空节点不入栈。二叉树的最大深度虽然我们之前写过了前中后序的迭代法代码但是并不代表迭代法的代码和递归中的前中后序对应非统一编写风格的迭代法只能模拟前序遍历后序遍历是通过翻转中序遍历是通过指针。统一编写风格的迭代法是可以利用栈来模拟递归和回溯的代码随想录中也说了有些递归算法的对应迭代法写起来的代码逻辑是很难的。非统一编写风格中因为空节点不入栈所以无法知道目前代码的处理逻辑在哪个节点。但是统一风格下有None的存在当遍历到叶子节点时我们可以通过pop四次得到左右叶子将处理的结果append进栈再append一个None我目前感觉这样的处理逻辑应该可行。求二叉树的最小深度有点乱了求最小深度前序和迭代不会写完全二叉树的节点个数平衡二叉树本题的迭代法太麻烦要先搞一个函数专门计算深度在搞另一个函数从前序开始遍历每一个节点去判断左右子树太复杂本题的迭代法不做学习。 二叉树的所有路径本题的迭代法在编写感觉上与递归稍有不同关键点在于搞清楚增加路径的逻辑应该放在哪里以及遇到叶子节点的处理逻辑是否需要加入最后一个节点的数值迭代法因为在初始化时要有根节点所以在加入路径的逻辑上与迭代法不同要注意体会。想不明白的时候就自己模拟试试。 迭代法模拟前中后序就用栈适合层序遍历就用队列。左叶子之和树左下角的值路径总和路径总和II用迭代法记录所有路径是很繁琐的这种题不适合迭代法一定要体会其中区别问“有没有”迭代法可以“找出所有可能”迭代法不行。递归函数什么时候需要返回值什么时候不需要前面两道路径总和的题可以在子节点判断后再加一个判断做剪枝前面两题我写的和代码随想录写的细节有些不同我是从空列表开始递归卡哥是先让根节点入栈了这一个差异就导致代码编写风格差异一看上去还挺大。中序后序建立二叉树前序中序建立二叉树这两题只要想清楚区间的左右边界就可以了过。最大二叉树同上一题都是构造的题目合并二叉树二叉搜索树中的搜索验证二叉搜索树(重要重要重要因为我一直不会)这道题我竟然还是不会看到二叉搜索树就要想到中序遍历中序遍历得到的数组是递增的。 二叉搜索树的最小绝对差二叉搜索树中的众数怎么bug一直调不好了这题有很多细节我没注意到下面的是错误的代码上述代码的致命错误大致如下首先是初始化上的错误两个计数器必须全部置0另外让根节点进去结果列表这是毫无道理的第二点就是没有处理好第一个节点最左下的节点当 pre 是 None 时我们应该将 count 赋值为 1 这样最左下的节点就可能作为结果。第三点对于当前节点是否是空节点的判断只能决定当前的 count 是多少而结果处理逻辑肯定是要放在 if 判断之外的不然也同样会漏掉最左下节点作为结果的情况。如果本题不是二叉搜索树而是一般二叉树就要利用字典了 二叉树的最近公共祖先二叉搜索树的最近公共祖先这道题因为有序树的存在思路和上一题完全不一样了本题的核心在于利用二叉搜索树的性质。需要理解的是按照如下规则找到的节点一定是最近的公共祖先因为一旦向下进入左右孩子必然会丢失掉 p q 中的一个。 二叉搜索树中的插入操作删除二叉搜索树中的节点这道题写下来还是蛮难的而且我感觉我现在的逻辑也没有很清晰加了不少 if 判断。我主要的思路就是删除当前节点后直接用当前节点的左孩子顶上来然后把当前节点的右子树加到左孩子的最右。这样就满足二叉搜索树的性质。但是还要处理很多特殊情况这也是我这么多 if 的由来比如我取了当前节点的左右孩子那么自然就要考虑如果是空怎么办都是空一个是空情况都要考虑清楚。只要取了节点的左右孩子还想取它的value就要想到判断是否是None。看看代码随想录的解答吧卡哥给出的普通树的删除方法以及迭代法都先不做学习了先掌握最基本的递归法。本题对于第五步删除拼接的情况本来就有两种选择上面我都提到了左接右右接左。 修剪二叉搜索树不会理不清处理逻辑。看看代码随想录的解答。这是一个思维转变的问题好好理解。这道题非常非常重要。迭代法先不做学习了、 将有序数组转换为二叉搜索树把二叉搜索树转换为累加树 本博客的内容只是做一个大概的记录整个PDF看下来内容上是不如代码随想录网站上的文章全面的并且PDF中有些地方的描述是很让我疑惑的在困扰我很久后无意间发现其网站上的讲解完全符合我的思路。这次看完这些PDF后暂时一段时间内不会再看了要复习还是依靠代码随想录网站视频和我自己写的博客吧
二叉树章节
二叉树章节做不出来的题基本上都有一个共性对二叉树的数据结构特性不熟悉从而没有编写思路或者在判断条件上产生疏漏。
完全二叉树除了最底层可能没填满其余每层节点数都达到最大值并且最下面一层的节点都集中在该层最左边的若干位置。一个很关键的点完全二叉树的某些子树一定是满二叉树节点数量是可以计算的。去计算最左和最后一直向左找计数一直向右找计数如果两数相等这颗子树就是满二叉树。
二叉搜索树若它的左子树不空则左子树上所有节点的值均小于它的根节点的值。若它的右子树不空则右子树上所有节点的值均大于它的根节点的值。它的左右子树也分别为二叉搜索树。
平衡二叉树它是一个空树或者它的左右两个子树的高度差的绝对值不超过1并且左右子树都是一颗平衡二叉树。
二叉树的链式存储是大家一直在用的那么其顺序存储要注意需要将树填补为一颗满二叉树才能满足公式如果父节点的数组下标是 i , 那么它的左孩子就是 i21右孩子是 i22 。
在遍历方式上主要分为两大类深度优先遍历前中后序遍历广度优先遍历层序遍历。层序遍历有时候是很好用的方法有的题用递归解法较复杂或者在代码编写逻辑上不好思考后面会提到。
深度优先遍历的三种方法中后序遍历是应用最多的因为很多时候我们都需要去收集左右子树的信息来决定当前节点的方式或者说需要将某些信息一层一层地返回到根节点这时候都需要后序遍历。中序遍历和二叉搜索树严格绑定。前序遍历需要的场景一般都有比较明显的特征可以意识到。
前序遍历中左右中序遍历左中右后序遍历左右中。 二叉树的节点定义
class TreeNode:def __init__(self, val, left None, right None):self.val valself.left leftself.right right递归三部曲
1、确定递归函数的参数和返回值。2、确定终止条件。3、确定单层递归的逻辑
判断了递归中不会有空节点就可以不写返回条件以前序遍历为例
两个版本代码的对比一个带空节点判断一个不带。
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)# 注意空节点不入栈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)# 空节点不入栈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:# 同样注意空节点不入栈if cur :stack.append(cur)cur cur.leftelse :cur stack.pop()res.append(cur.val)cur cur.rightreturn res上面三种迭代方法需要注意的共同点是迭代法中要保证空节点不入栈。
前中后序遍历的统一迭代方法
以中序遍历为例因为是迭代法使用的是栈作为数据结构在代码中的编写顺序和在结果集中的保存顺序是不一样的。代码编写是右中左结果集中就是左中右
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不是空节点时的操作是关键# 要根据遍历顺序重新调整元素顺序# 因为是使用堆栈所以要从下向上看左中右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 res117. 填充每个节点的下一个右侧节点指针 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 root104.二叉树的最大深度
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 depth111.二叉树的最小深度
需要注意的是只有当左右孩子都为空的时候才说明遍历的最低点了。如果其中一个孩子为空则不是最低点.
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上面求最大深度和最小深度的题目我们后面还会遇到可以发现其实递归也不一定比迭代法好用只不过能不能想的到使用层序遍历就是需要修炼的了。
226.翻转二叉树通过本题希望学会如何将递归方法中的逻辑写在相对应的迭代法中
本题用什么遍历顺序
对于使用基于递归的方法来说前序后序层序都可以。唯独中序不行。这个自己画画图就可以知道。
对于使用迭代的方法来说同递归。这里的迭代指的是不加入None的迭代法
对于使用统一方式迭代的方法来说任何顺序都可以。
递归代码前序遍历
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统一迭代风格的C代码中序遍历
class Solution {
public:TreeNode* invertTree(TreeNode* root) {stackTreeNode* 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); // 节点处理逻辑}}return root;}
};为什么这个中序就是可以的呢因为这是用栈来遍历而不是靠指针来遍历避免了递归法中翻转了两次的情况。
只要是能编写出相应迭代法的递归法在时间复杂度上二者差不多在空间复杂度上迭代法要优于递归。因为递归需要系统堆栈存储参数返回值等信息。
通过上一题我们要意识到非统一版本的迭代法前序和后序都是基于栈的也是靠栈来遍历的而非统一版本的迭代法的中序遍历是靠指针来遍历的。这二者是不同的。而统一版本的迭代法前中后序都是基于栈来遍历的。
对称二叉树
这道题就是后序遍历但是我觉得在编写风格上对我来说总感觉这不是后序遍历用前序遍历的逻辑就写出来了似乎我还没有完全掌握这道题。 递归法
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迭代法没写出来困惑点在于在判断时需要考虑空节点但是迭代法的空节点应该不能入栈的 使用队列
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: #左节点为空、右节点为空此时说明是对称的continue#左右一个节点不为空或者都不为空但数值不相同返回falseif not leftNode or not rightNode or leftNode.val ! rightNode.val:return Falsequeue.append(leftNode.left) #加入左节点左孩子queue.append(rightNode.right) #加入右节点右孩子queue.append(leftNode.right) #加入左节点右孩子queue.append(rightNode.left) #加入右节点左孩子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)# 注意层次遍历这里空节点也要入栈的这样才能比较else:level_vals.append(None)if level_vals ! level_vals[::-1]:return Falsereturn True经过上一题学会了如何处理在迭代法中要处理空节点的情况。统一风格的迭代法中因为要用空节点来标记要处理的中间节点就不能再让空节点入栈了。中序迭代遍历也不行因为中序迭代法是需要指针来指示当前位置的所以也要求空节点不入栈。
前序遍历
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二叉树的最大深度
根节点的高度等于最大深度后序遍历很好写。求高度是自底向上的用后序遍历。求深度是自顶向下的用前序遍历。 高度求解法
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,depth1)self.digui(root.right,depth1)迭代法求深度
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,depth1))if cur.right :stack.append((cur.right,depth1))return maxd层序遍历法 套用模板即可。
统一编写风格的迭代法
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,depth1))# 右if cur.right :stack.append((cur.right,depth1))# 那么在栈中的顺序就是右左中当然这里什么顺序都不是了因为不需要回溯只需要记录每次的depthelse :(cur,depth) stack.pop()maxd max(maxd,depth)return maxd虽然我们之前写过了前中后序的迭代法代码但是并不代表迭代法的代码和递归中的前中后序对应非统一编写风格的迭代法只能模拟前序遍历后序遍历是通过翻转中序遍历是通过指针。统一编写风格的迭代法是可以利用栈来模拟递归和回溯的代码随想录中也说了有些递归算法的对应迭代法写起来的代码逻辑是很难的。
非统一编写风格中因为空节点不入栈所以无法知道目前代码的处理逻辑在哪个节点。但是统一风格下有None的存在当遍历到叶子节点时我们可以通过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 1rightelif left ! 0 and right 0 :return 1left# 这个判断条件冗余了和下面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完全二叉树的节点个数
利用完全二叉树的性质提前判断。但归根结底还是后序遍历。
如果是一般二叉树可以递归可以层序遍历但是想要利用完全二叉树的性质只能递归。
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,cleft1)-1return numberelse :return 1 self.count_fun(root.left) self.count_fun(root.right)平衡二叉树
一开始是想就用题目给的 isBalanced 函数一个函数解决问题但是发现要从叶子节点计算高度所以还得两个函数。
在一个就是本题别想着整个在迭代开始前的判断剪枝其实省不了多少空间还可能导致返回值异常的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本题的迭代法太麻烦要先搞一个函数专门计算深度在搞另一个函数从前序开始遍历每一个节点去判断左右子树太复杂本题的迭代法不做学习。
二叉树的所有路径
本题我采用了字符串作为承载路径的数据结构之前我一直习惯用的是列表可以放心大胆的 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) -)本题的迭代法在编写感觉上与递归稍有不同关键点在于搞清楚增加路径的逻辑应该放在哪里以及遇到叶子节点的处理逻辑是否需要加入最后一个节点的数值迭代法因为在初始化时要有根节点所以在加入路径的逻辑上与迭代法不同要注意体会。
想不明白的时候就自己模拟试试。
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迭代法前序遍历统计每一个左叶子就好了。
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树左下角的值
本题使用层序遍历思路非常简单是层序遍历的模板题这里我使用递归。
递归要使用前序遍历这样才能优先左边搜。
class Solution:def findBottomLeftValue(self, root: Optional[TreeNode]) - int:self.maxdepth 0# 如果depth初值给0的话因为一开始会等于maxdepth就要单独判断二叉树只有一个# 根节点的情况了如果给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,depth1)self.find_left(root.right,depth1)路径总和
第一次自己尝试编写代码随想录风格的利用设置返回值找到就返回的递归代码。
需要注意的还是那一点理清处理逻辑递归函数怎么写需不需要回溯需要回溯想写成隐式的怎么写显式的怎么写在收获结果的时候处理逻辑怎么写终止条件怎么写。
class Solution:def hasPathSum(self, root: Optional[TreeNode], targetSum: int) - bool:if root None :return False# 注意处理逻辑一开始这里最后一个条件我写的是targetSum 0 一直错误# 后来才发现我没有去处理最后一个节点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()用迭代法记录所有路径是很繁琐的这种题不适合迭代法一定要体会其中区别问“有没有”迭代法可以“找出所有可能”迭代法不行。
递归函数什么时候需要返回值什么时候不需要
如果需要搜索整棵二叉树且不用处理递归返回值递归函数就不要返回值。这种情况就是本文下半部分介绍的113.路径总和ii
如果需要搜索整棵二叉树且需要处理递归返回值递归函数就需要返回值。 这种情况我们在236. 二叉树的最近公共祖先 (opens new window)中介绍
如果要搜索其中一条符合条件的路径那么递归一定需要返回值因为遇到符合条件的路径了就要及时返回。本题的情况
前面两道路径总和的题可以在子节点判断后再加一个判断做剪枝 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但是一定要注意顺序要放在判断当前叶子节点不符合要求之后。
前面两题我写的和代码随想录写的细节有些不同我是从空列表开始递归卡哥是先让根节点入栈了这一个差异就导致代码编写风格差异一看上去还挺大。
中序后序建立二叉树前序中序建立二叉树这两题只要想清楚区间的左右边界就可以了过。
最大二叉树同上一题都是构造的题目
合并二叉树
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
构造树一般采用的是前序遍历因为先构造中间节点然后递归构造左子树和右子树。
迭代法代码随想录给的是用对队列但是并不是层序遍历的模板用栈作为容器一样可以这里我是用的栈。
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的赋值操作这时候再判断本来一空一不空# 现在变成都不空了出现错误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)二叉搜索树因为其结构特殊性的存在不需要回溯操作所以不需要栈或队列来模拟递归。直接循环
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验证二叉搜索树(重要重要重要因为我一直不会)
这道题我竟然还是不会
现在能想到避开陷阱不是仅仅比较左右孩子就可以的
但是依然忘了迭代法怎么编写
递归法就是先中序遍历得到数组再遍历数组。
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这里用递归法的一个技巧在于声明一个全局变量节点。
class Solution:def __init__(self):self.pre None # 用来记录前一个节点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 # 记录前一个节点right self.isValidBST(root.right)return left and right迭代法
class Solution:def isValidBST(self, root):stack []cur rootpre None # 记录前一个节点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.minabsclass 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一直调不好了这题有很多细节我没注意到下面的是错误的代码
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另外让根节点进去结果列表这是毫无道理的第二点就是没有处理好第一个节点最左下的节点当 pre 是 None 时我们应该将 count 赋值为 1 这样最左下的节点就可能作为结果。第三点对于当前节点是否是空节点的判断只能决定当前的 count 是多少而结果处理逻辑肯定是要放在 if 判断之外的不然也同样会漏掉最左下节点作为结果的情况。
正确代码
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 # 统计元素频率self.searchBST(cur.left, freq_map)self.searchBST(cur.right, freq_map)def findMode(self, root):freq_map defaultdict(int) # key:元素value:出现频率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本题没有迭代法本题的讲解写的很好可以多读读。 最近公共祖先
二叉搜索树的最近公共祖先
又没写出来错误代码如下。受上一题影响总想在上一题的基础上稍作改动但是发现在二叉搜索树中同时匹配两个值是不现实的逻辑会非常混乱。
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 这道题因为有序树的存在思路和上一题完全不一样了本题的核心在于利用二叉搜索树的性质。需要理解的是按照如下规则找到的节点一定是最近的公共祖先因为一旦向下进入左右孩子必然会丢失掉 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)既然本题已经无所谓遍历顺序变成了一道寻找二叉搜索树的节点的题目迭代法自然可行且简便了。
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二叉搜索树中的插入操作
本题要注意的是一定要写递归函数返回值利用返回值去修改二叉树如果没有修改返回值就是原本树的自身。
另外本题要理解明确只往空节点插入就可以了不要想着更改树的结构。
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删除二叉搜索树中的节点
这道题写下来还是蛮难的而且我感觉我现在的逻辑也没有很清晰加了不少 if 判断。我主要的思路就是删除当前节点后直接用当前节点的左孩子顶上来然后把当前节点的右子树加到左孩子的最右。这样就满足二叉搜索树的性质。但是还要处理很多特殊情况这也是我这么多 if 的由来比如我取了当前节点的左右孩子那么自然就要考虑如果是空怎么办都是空一个是空情况都要考虑清楚。
只要取了节点的左右孩子还想取它的value就要想到判断是否是None。看看代码随想录的解答吧
我的代码目标删除节点的右孩子往目标删除节点的左孩子的最右去接
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删除二叉搜索树中的节点 卡哥给出的普通树的删除方法以及迭代法都先不做学习了先掌握最基本的递归法。
根据卡哥给的思路对上面自己的代码进行了小修改思路是目标删除节点的左孩子往目标删除节点的右孩子的最左去接。
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:# 寻找符合区间 [low, high] 的节点return self.trimBST(root.right, low, high)if root.val high:# 寻找符合区间 [low, high] 的节点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
