秋叶红霜CCCCCC - 个人主页动态

2022-10-28 01:35

python3，非递归方法，对称性，对应着回文性。对左右子树分别做层次遍历，各自维护一个栈，因为对称性对应着回文性，所以入栈的顺序变一下，则对称性必会导致栈相同，如果不同则无对称性 class Solution: def isSymmetrical(self , pRoot: TreeNode) -> bool: if not pRoot: return True #辅助队列用于从两边层次遍历 l1 = [] l2 = [] l1.append(pRoot.left) l2.append(pRoot.right) while l1 and l2: # 左右两个栈，弹出 l = l1.po...

0 点赞评论收藏

2022-10-28 00:20

中国科学技术大学算法工程师

题解 | #二叉树中和为某一值的路径(三)#

python3 DFS + 哈希表，双O(n)复杂度。   利用哈希表维护：从根出发的路径和 及其 对应的条数。   当前节点，如果是这样的情况：当前累加和temp - 目标和sum 在哈希表出现，则意味着出现了累加和sum，累加和sum的条数就是temp - sum的条数。如果没出现temp - sum，也就没出现sum。当前累加和同理，出现了则+1，没出现作为键写入哈希表，值为1。   （temp - sum + sum = temp，总和temp，temp-sum的条数就是sum的条数，想象一张琴的琴弦（两端都固定在一点上的），一端有多条路径和为temp-sum的路，那么自然也有同样多条...

0 点赞评论收藏

2022-10-27 22:52

中国科学技术大学算法工程师

题解 | #序列化二叉树#

 序列化和反序列化，意味着做一个可逆变换。可逆变换也就是一一映射，保留所有的原始信息，都要序列化 。   用层次遍历。   序列化的时候：注意数值转换为字符。   反序列化的时候：逐次遍历字符串解绑后的数组，对栈循环，数组是none，就不操作，不是none就作为栈弹出的结点的左结点或右结点。用栈添加下一层。   class Solution:     def Serialize(self, root):         if ...

0 点赞评论收藏

2022-10-27 21:55

中国科学技术大学算法工程师

题解 | #序列化二叉树#

很骚的方法，能过测例。虽然不是出题的目的。   class Solution:     def Serialize(self, root):         self.root = root         return None     def Deserialize(self,&nbs...

0 点赞评论收藏

2022-10-27 21:15

中国科学技术大学算法工程师

题解 | #二叉树的下一个结点#

python3，非递归法。   利用中序遍历的性质：     如果有右结点，中序遍历下一个就是右结点   如果没有右结点：     如果有父结点，且是父结点的左结点，返回父结点。   如果有父结点，且是父结点的右结点，则循环继续向上，寻找一个父结点让自己是左结点。循环到树的根为止。   没父结点，或者循环到根都没有找到合适的父结点，都返回None     class Solution:     def GetNext(self, pNode):       &nbs...

0 点赞评论收藏

2022-10-27 14:08

中国科学技术大学算法工程师

题解 | #判断是不是平衡二叉树#

Python3递归。所谓自底向上，就是利用非平衡的传染性：有非平衡子树，自己一定非平衡。所以只要子树出现非平衡，就返回-1（非正常深度，正常的深度>=0），子树都平衡，才计算高度差并返回   class Solution:     # 自底向上，非平衡直接返回-1（-1有传染性，即非平衡往上直接判断非平衡）。平衡再计算深度返回     def IsBalanced_Solution(self, pRoot):      ...

0 点赞评论收藏

2022-10-27 13:45

中国科学技术大学算法工程师

题解 | #判断是不是平衡二叉树#

python3，递归   class Solution:     def IsBalanced_Solution(self , pRoot: TreeNode) -> bool:         def depth(root):             if no...

0 点赞评论收藏

2022-10-27 12:54

中国科学技术大学算法工程师

题解 | #二叉搜索树与双向链表#

python3，典型的中序遍历   中序遍历，两个指针记录前驱结点和后驱结点，递归后驱结点，为空时前驱结点到达尾部（即最大/最右）。如果要求做成循环列表，额外连上首尾即可。   class Solution:     def Convert(self , pRootOfTree ):         def dfs(cur):        &nb...

0 点赞评论收藏

2022-10-27 11:42

中国科学技术大学算法工程师

题解 | #二叉树中和为某一值的路径(二)#

Python3 深度优先搜索，维护一个路径列表。如果规定了结点值的正负性，还可以剪枝。否则，这里只能递归到叶子结点了。叶子节点且满足和的条件，把path加入res结果集。满足不满足，都要把节点踢出path，以便其他路径的递归。   class Solution:     def FindPath(self , root: TreeNode, target: int) -> List[List[int]]:     &nb...

0 点赞评论收藏

2022-10-27 02:30

已编辑

中国科学技术大学算法工程师

题解 | #二叉搜索树的后序遍历序列#

python3，时间复杂度O(n)的非递归方法。   BST的后序遍历是左右中，逆序后序遍历，就变成了中右左。BST的性质，右一定是大于中的，左一定是小于中的。   设置一个比较参数root，初始化是无穷大。   根部先入栈，如果元素比栈顶大，则是右结点（root是不允许出现左结点后再出现右结点，如果一直是右结点，自然不改变），直接入栈；如果元素比栈顶小，必是左结点，此时找出是谁的左结点，以此更新为root（因为根右左嘛，一旦该结点出现了左结点，就一定不会再出现右结点了）。   class Solution:     def Veri...

0 点赞评论收藏

2022-10-27 01:35

中国科学技术大学算法工程师

题解 | #二叉搜索树的后序遍历序列#

python3，非递归方法。   理解：   所谓后序遍历，尾部一定是最“中”性的。   体现在BST中，即任意尾部，相对于该尾部之前，一定是中等大小的，等价表述：对于任意尾部，最多，经过一轮小于尾部的迭代，再经过一轮大于尾部的迭代，就一定可以到达尾部。   BST一定满足这个特征，满足这个特征的一定可以做成BST。   class Solution:     def VerifySquenceOfBST(self , sequence: List[int]) -> bool: ...

0 点赞评论收藏

2022-10-27 00:45

中国科学技术大学算法工程师

题解 | #二叉搜索树的后序遍历序列#

递归：   长度<=2，一定可以做成BST。   长度>2，尾部元素一定是根结点。   BST的特征：全部大于根；全部小于根；左子树小于根，右子树大于根。   class Solution:     def VerifySquenceOfBST(self , sequence: List[int]) -> bool:         # 方法：利用根节点的位置，划分左右子树，再进...

0 点赞评论收藏

2022-10-26 22:11

中国科学技术大学算法工程师

题解 | #树的子结构#

python3，递归方法。   子结构内的递归：子结构，意味着从头到子树递归的匹配上。       如果子结构递归到空，即意味着完成了全部匹配，返回True。如果子结构没递归到空且这时树递归到空了，即意味着不够匹配，返回False；或者结点不相等，匹配失败，返回False。   子结构头的递归：如果以当前树结点作为子结构的头，匹配不上，这个头也要在树内递归的变化。       如果子结构是空树，直接返回False，如果子结构的头（树结点）是空，不够匹配，返回False。如果树当前结点作为头，递归成功，则返回True；或者换头之后匹配成功，也返回True，...

0 点赞评论收藏

2022-10-26 20:32

中国科学技术大学算法工程师

题解 | #重建二叉树#

充分说明了本质：前序是“根”的排序，即按最“根”来排序；中序是“左”的排序，即按最“左”来排序。 而这两者具有“部分矛盾性”（左根和根左），从前序的角度来描述，即：           矛盾不发生时（互不打扰时）：前序正在进行根左。           矛盾发生时（同时进行时）：根左和左根是矛盾点，只能寻找相容点，那就是“根-右”或“左-右”。   利用这个“部分矛盾性”，可以区分是左子结点，还是右子结点或左右兄弟（这两者可合在一起考虑）的情况。     ...

0 点赞评论收藏

2022-10-26 14:14

中国科学技术大学算法工程师

题解 | #按之字形顺序打印二叉树#

层次遍历，只需考虑每一层的结果出来之后，是从左到右的顺序添加，还是从右到左的顺序添加。可以用一个Flag标志，也可以根据结果集的长度的奇偶性标志。   class Solution:     def Print(self, pRoot: TreeNode) -> List[List[int]]:         queue = []     &nbsp...

0 点赞评论收藏

创作者周榜

关注他的用户也关注了：