中序遍历classTreeNode(object):def__init__(self,x):self.valx self.leftNoneself.rightNonedefin_order_traversal(root):# 中序res[]stack[]#借用栈ifrootisNone:returnres currootwhilelen(stack)!0orcurisnotNone:whilecurisnotNone:stack.append(cur)curcur.left nodestack.pop()res.append(node.val)curnode.rightreturnres# 中序打印二叉树递归definOrderTraverse(node):ifnodeisNone:returnNoneinOrderTraverse(node.left)print(node.val)inOrderTraverse(node.right)前序遍历classTreeNode(object):def__init__(self,x):self.valx self.leftNoneself.rightNonedefpre_order_traversal(root):# 前序result[]stack[]stack.append(root)whilelen(stack)!0:nodestack.pop()ifnodeisNone:continueresult.append(node.val)stack.append(node.right)stack.append(node.left)returnresult# 先序打印二叉树递归defpreOrderTraverse(node):ifnodeisNone:returnNoneprint(node.val)preOrderTraverse(node.left)preOrderTraverse(node.right)后序遍历classTreeNode(object):def__init__(self,x):self.valx self.leftNoneself.rightNonedefpost_order_traversal(root):# 后序 前序遍历为 root - left - right后序遍历为 left - right - root 可以修改前序遍历成为 root - right - left那么这个顺序就和后序遍历正好相反 result[]stack[]stack.append(root)whilelen(stack)!0:nodestack.pop()ifnodeisNone:continueresult.append(node.val)stack.append(node.left)stack.append(node.right)returnresult[::-1]# 后序打印二叉树递归defpostOrderTraverse(node):ifnodeisNone:returnNonepostOrderTraverse(node.left)postOrderTraverse(node.right)print(node.val)从上往下打印二叉树简单题目描述从上往下打印出二叉树的每个节点同层节点从左至右打印。思路根节点不存在 返回空开辟queue空间 初始化为[root] 队列意味着一层一层的遍历开辟放结果的数组 res当队列不为空时while计算这一层有几个节点n遍历这一层for如果这一层不存在节点 退出for循环否则 取出一个节点 添加到放结果的数组res将下一层的节点都添加到队列 即如果该节点左右节点存在添加到队列返回res运行时间26ms占用内存5860kclassTreeNode:def__init__(self,x):self.valx self.leftNoneself.rightNonedefconstruct_tree():rootTreeNode(8)root.leftTreeNode(6)root.rightTreeNode(10)root.left.leftTreeNode(5)root.left.rightTreeNode(7)root.right.leftTreeNode(9)root.right.rightTreeNode(11)root.left.right.leftTreeNode(12)root.left.right.rightTreeNode(13)returnrootclassSolution:# 返回从上到下每个节点值列表例[1,2,3]defPrintFromTopToBottom(self,root):# write code hereifnotroot:return[]queue[root]res[]whilequeue:nlen(queue)for_inrange(n):ifnotqueue:breaktempqueue.pop(0)res.append(temp.val)iftemp.left:queue.append(temp.left)iftemp.right:queue.append(temp.right)returnres sSolution()treeconstruct_tree()ress.PrintFromTopToBottom(tree)print(res)#return [8, 6, 10, 5, 7, 9, 11, 12, 13]按之字形打印二叉树题目描述请实现一个函数按照之字形打印二叉树即第一行按照从左到右的顺序打印第二层按照从右至左的顺序打印第三行按照从左到右的顺序打印其他行以此类推。思路同上一道题不同之处在于添加了标记偶数行的标记 jj 初始化为-1 每开始新一行的循环 j 就加一最后每一行遍历完后 判断这是奇数行还是偶数行偶数行的话反转这一行的数值。第二个不同之处在于开辟了放每一行数值的暂存数组temp因为偶数行的话必须反转后才能添加到结果数组res里面。运行时间27ms占用内存5728kclassSolution:defPrint(self,pRoot):# write code hereifnotpRoot:return[]res[]#放结果的数组queue[pRoot]j-1#标记偶数行whilequeue:j1nlen(queue)temp[]#放这一行的节点数值for_inrange(n):nodequeue.pop(0)temp.append(node.val)ifnode.left:queue.append(node.left)ifnode.right:queue.append(node.right)ifj%2:#当j表示这一行为偶数行 反转这一行temp.reverse()res.append(temp)#把这一行确定的节点数值放进结果数组里returnres sSolution()treeconstruct_tree()ress.Print(tree)print(res)把二叉树打印成多行题目描述从上到下按层打印二叉树同一层结点从左至右输出。每一层输出一行。运行时间25ms占用内存5632kclassSolution:# 返回二维列表[[1,2],[4,5]]defPrint(self,pRoot):# write code hereifnotpRoot:return[]queue[pRoot]res[]whilequeue:nlen(queue)temp[]for_inrange(n):nodequeue.pop(0)temp.append(node.val)ifnode.left:queue.append(node.left)ifnode.right:queue.append(node.right)res.append(temp)# print(res)returnres#return [[8], [6, 10], [5, 7, 9, 11]]对称的二叉树题目描述请实现一个函数用来判断一颗二叉树是不是对称的。注意如果一个二叉树同此二叉树的镜像是同样的定义其为对称的。思路如果根节点不存在 返回真把每一层放进队列 queue [pRoot]当队列里有节点时 进行以下操作看这一层有多少个节点 n如果非根节点且这一层节点数是奇数则返回false否则重点判断这一行最左和最右是否一样【判断两个节点一样么两节点都不存在则两节点一样两节点都存在且数值一样则两节点一样否则返回不一样】遍历这一行弹出队列中的一个节点如果该节点不存在 过否则将下一层的节点都添加到队列 即如果该节点左右节点存在添加到队列运行时间25ms占用内存5732kclassSolution:defisEqual(self,p1,p2):ifnotp1andnotp2:returnTrueelifp1andp2andp1.valp2.val:returnTrueelse:returnFalsedefisSymmetrical(self,pRoot):# write code hereifnotpRoot:returnTruequeue[pRoot]whilequeue:# print(queue)nlen(queue)ifqueue[0]!pRootandn%2!0:returnFalseforiinrange(n//2):ifnotself.isEqual(queue[i],queue[-1-i]):returnFalsefor_inrange(n):nodequeue.pop(0)ifnotnode:continuequeue.append(node.left)queue.append(node.right)returnTrue二叉树的下一个结点题目描述给定一个二叉树和其中的一个结点请找出中序遍历顺序的下一个结点并且返回。注意树中的结点不仅包含左右子结点同时包含指向父结点的指针。思路分情况讨论第一节点p的右节点存在p的下一个节点 则为p的右子树的最左节点 [1.1】第二节点p的右节点不存在的话 分两种情况第一 节点p的右节点不存在的话 且 p为其父节点的左子节点p的下一个节点 则为p的父节点 【2.1】第二节点p的右节点不存在的话 且 p为其父节点的右子节点 p的下一个节点 为 沿着父节点往上遍历 找到一个点 满足该点是其父节点的左子节点。若该点不存在则p的下一个节点不存在【2.2】如果该节点为空 返回Nonep的右节点存在的话找到右子树的最左节点 返回节点p的右节点不存在的话 且 p为其父节点的右子节点 时关键往上遍历 当pNode是自己父节点的左子节点时跳出while返回pNode的父节点运行时间26ms占用内存5864kdefconstruct_tree():rootTreeNode(1)root.leftTreeNode(2)root.rightTreeNode(3)root.left.leftTreeNode(4)root.left.rightTreeNode(5)root.right.leftTreeNode(6)root.right.rightTreeNode(7)root.left.right.leftTreeNode(8)root.left.right.rightTreeNode(9) root TreeNode(a) root.left TreeNode(b) root.right TreeNode(c) root.left.left TreeNode(d) root.left.right TreeNode(e) root.right.left TreeNode(f) root.right.right TreeNode(g) root.left.right.left TreeNode(h) root.left.right.right TreeNode(i) root.parentNoneroot.left.parentroot root.right.parentroot root.left.left.parentroot.left root.left.right.parentroot.left root.right.left.parentroot.right root.right.right.parentroot.right root.left.right.left.parentroot.left.right root.left.right.right.parentroot.left.rightreturnrootclassTreeNode:def__init__(self,x):self.valx self.leftNoneself.rightNoneself.parentNoneclassSolution:defGetNext(self,pNode):# write code hereifnotpNode:returnNoneifpNode.right:#ppNode.rightwhilep.left:pp.leftreturnp#whilepNode.parentandpNode.parent.rightpNode:pNodepNode.parentreturnpNode.parent rootconstruct_tree()sSolution()#ress.GetNext(root.left.left)ress.GetNext(root.right.left)print(res.val)二叉树的深度题目描述输入一棵二叉树求该树的深度。从根结点到叶结点依次经过的结点含根、叶结点形成树的一条路径最长路径的长度为树的深度。思路队列queue 用来放每一层节点运行时间28ms占用内存5728kclassSolution:defTreeDepth(self,pRoot):# write code hereifnotpRoot:return0#根节点不存在 返回0queue[pRoot]# 把每一层放进队列deep0#深度初始化为0whilequeue:#当这一层有节点时nlen(queue)#看着一层有几个节点nfor_inrange(n):#遍历这一层的n个节点nodequeue.pop(0)#弹出一个并把弹出的节点的下一层的节点即左右子节点添加到队列ifnode.left:queue.append(node.left)ifnode.right:queue.append(node.right)deep1#每一层遍历完 深度加一returndeep二叉搜索树的第k个结点题目描述给定一棵二叉搜索树请找出其中的第k小的结点。例如 5372468 中按结点数值大小顺序第三小结点的值为4。运行时间26ms占用内存5864k树的子结构题目描述输入两棵二叉树AB判断B是不是A的子结构。ps我们约定空树不是任意一个树的子结构重建二叉树中等题目描述输入某二叉树的前序遍历和中序遍历的结果请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}则重建二叉树并返回。思路用前序遍历找到根结点用根结点在中序遍历中切开左右子树递归重建二叉树前序数组为空时返回空用前序遍历找到根结点初始化一个为根值的树节点遍历后序数组找到根数值的索引位置i切分左右子树,递归调用本函数返回根节点运行时间42ms占用内存5724k# class TreeNode:# def __init__(self, x):# self.val x# self.left None# self.right NoneclassSolution:# 返回构造的TreeNode根节点defreConstructBinaryTree(self,pre,tin):# write code hereifnotpre:returnroot_valpre[0]rootTreeNode(root_val)foriinrange(len(tin)):iftin[i]root_val:breakroot.leftself.reConstructBinaryTree(pre[1:1i],tin[:i])root.rightself.reConstructBinaryTree(pre[1i:],tin[i1:])returnroot用两个栈来实现一个队列完成队列的Push和Pop操作。 队列中的元素为int类型。