【剑指offer】序列化二叉树（python） 1. python的嵌套函数， 闭包和函数工厂是嵌套函数最重要的用处。如果你看到一个带装饰器的函数，这个装饰器就是一个函数工厂，它以一个函数作为参数，并返回一个新的函数，新的函数使用闭包包括了作为参数的函数。换句话说，装饰器就是一个语法糖，语法糖就是一种便捷写法。 嵌套函数封装了一些函数过程，对于全局命名空间来说，它们是隐藏的。 嵌套函数可以避免自我重复。在大型函数中，可能会重复使用一些代码，比方说，我们写一个处理文件的函数，同时支持文件名或文件对象作为参数： def process(file_name): def do_stuff(...

【剑指offer】二叉搜索树与双向链表（python） 思路：将所有结点中序遍历到一个列表，因为是左中右遍历，因为二叉搜索树自身的性质，所以遍历后就是升序的有序数组，这是再让每个结点（最后一个结点不用设置）的right设为下一个结点，left设为上一个结点。 1. python 的enumerate() 函数用于将一个可遍历的数据对象(如列表、元组或字符串)组合为一个索引序列，同时列出数据和数据下标，一般用在 for 循环当中。返回 enumerate(枚举) 对象。 enumerate(sequence, [start=0]) 2. a[:-1] 除...

【剑指offer】二叉树中和为某一值的路径（python） python创建新列表的方法之一，就是直接把元素用方括号括起来，这里 return [str(root.val)] 就直接返回了一个列表。 DFS深度遍历，得到所有路径，再判断路径和是否等于目标值。 map() 会根据提供的函数对指定序列做映射。map(function, iterable, ...)第一个参数 function 以参数序列中的每一个元素调用 function 函数，返回包含每次 function 函数返回值的新列表。这里直接用了一个 int 做类型转换。 DFS中直接使用 += 做列表合并。包括 [str(root...

【剑指offer】二叉搜索树的后序遍历序列（python） 思路类似于“树的子结构”1.二叉搜索树的性质若它的左子树不空，则左子树上所有结点的值均小于它的根节点的值； 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值； 它的左、右子树也分别为二叉搜索树。2. 根据序列的最后一位确认出根节点，因为二叉树左子树都小于根节点，右子树都大于根节点，所以由根节点确定左子树最后一位，从而得到右子树开始的点，验证右子树是否都大于根节点，递归验证左右两子树。 class Solution: def VerifySquenceOfBST(self, sequence): # ...

【剑指offer】按之字形顺序打印二叉树（python） 思路类似于“把二叉树打印成多行”，添加一个flag，表示从左到右还是从右到左，如果是从右到左就把tmp反转添加到result里。 # -*- coding:utf-8 -*- # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution: def Print(self, pRoot): # writ...

【剑指offer】把二叉树打印成多行（python） 思路类似“从上往下打印二叉树”，也是用队列 有个小点，tmp需要判断是否为空。因为多遍历了一遍，最后一遍的时候tmp=[] # -*- coding:utf-8 -*- # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution: # 返回二维列表[[1,2],[4,5]] def Print(self,...

【剑指offer】从上往下打印二叉树（python） python列表的remove(val)方法可以删除特定val值，但不能返回，pop()就可以删除而且可以返回原值，默认使用-1，因此pop(0)将返回头元素，而pop()或pop(-1)则会返回列表的尾元素。这里用列表实现队列的功能，所以需要pop(0) 使用一个队列来遍历 因为完全二叉树的特殊属性，开始遍历一层的节点时，当前队列中的节点数就是当前层的节点数。 continue语法。Python continue 语句跳出本次循环，而break跳出整个循环。continue 语句用来告诉Python跳过当前循环的剩余语句，然后继续进行下...

【剑指offer】对称的二叉树（Python） 解题思路很像“树的子结构”那题。 # -*- coding:utf-8 -*- # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution: def Define(self,A,B): if not A and not B: return True if not A ...

【剑指offer】二叉树的镜像（python） 递归解决，先遍历左子树，交换左右孩子，然后遍历右子树，交换左右孩子，类似于后序遍历。 # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None # # 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 # # # @param pRoot TreeNode类 # @return TreeNode类 # class Solution...

【剑指offer】树的子结构（python） 遍历二叉树A，如果有和二叉树B相同的结点，再进行进一步判断。 进一步判断结构是否相同。如果结点值相同，递归判断它们各自的左右结点值是不是相同。递归终止条件是到达了树A或树B的叶节点。如果树B为空，遍历完了，说明是树A的子树，如果树A为空，说明树B结构大于树A，在树A中不存在。 # -*- coding:utf-8 -*- # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.r...

【剑指offer】二叉树的下一个结点（python） 分两种情况，一个是当前结点有右子树，一个是当前结点没有右子树。有右子树：返回该右子树的最左结点，往左遍历即可没有右子树：向上找父节点，该父节点的左孩子需等于当前结点，当前结点向上遍历。 class Solution: def GetNext(self, pNode): # write code here if pNode.right: p = pNode.right while p.left: p = p.left ...

【剑指offer】重建二叉树（python） 记住没有中序遍历结果是不能重建二叉树的！ 二叉树的左中后遍历顺序。前序遍历：根结点 ---> 左子树 ---> 右子树中序遍历：左子树---> 根结点 ---> 右子树后序遍历：左子树 ---> 右子树 ---> 根结点前序遍历：1 2 4 5 7 8 3 6中序遍历：4 2 7 5 8 1 3 6后序遍历：4 7 8 5 2 6 3 1 根据前序和中序遍历重建二叉树。前序中第一位是根节点，在中序中定位出根节点，左边就是左子树，右边是右子树，得到左子树的长度后，在前序序...

【剑指offer】两个链表的第一个公共结点（python） 纪念一下，第一次一遍过！很棒，加油！思路是双指针，一个遍历链表1，一个遍历链表2，需要注意的是指针复制的地方，链表2的指针是外部的，不需要复制，遍历到尾部就拉倒了，但是链表1的指针是内部的，需要复制，复制的地方在外循环内、内循环外。 # class ListNode: # def __init__(self, x): # self.val = x # self.next = None # # # @param pHead1 ListNode类 # @param pHead2 ListNod...

【剑指offer】复杂链表的复制（python） 递归终止条件。if pHead is None: return # -*- coding:utf-8 -*- # class RandomListNode: # def __init__(self, x): # self.label = x # self.next = None # self.random = None class Solution: # 返回 RandomListNode def Clone(self, pHead): # write co...