美文网首页
剑指offer--algorithm3

剑指offer--algorithm3

作者: strive鱼 | 来源:发表于2018-04-26 15:05 被阅读0次

归零后才能重新出发,不留遗憾才是最好的故事。

  • 本节的两题实际上介绍了两种重要且常见的数据结构,一个为树,一个为栈和队列

题 5 --重建二叉树

关于树的考察,书中有这样的描述,一般指的为二叉树--每一个节点都有两个子节点,而考察二叉树,一般考察的为遍历 。关于树的题目多变,但是一般解决方法都是通过前序遍历、中序遍历、后序遍历等遍历思路,而每一种思路都有递归跟循环两种方法。
image.png
下开始解题
关于重建二叉树的思路,书中主要是根据前序遍历和中序遍历的两种遍历方式进行分析,分析的相当到位,只能盗图
image.png
image.png

程序代码如下:

class treenode(object):#定义一个树的节点
    def __init__(self,a):
        self.value=a
        self.left=None#定义左节点
        self.right=None#定义右节点

class solution(object):
    def reconstructiontree(self,pre,med):
        if not pre and not med:#如果为空,则返回None 
            return None 
        if set(pre)!=set(med):#如果两者不相等则说返回None
            return None 
        i=med.index(pre[0])#确定根节点的位置
        root=treenode(pre[0])#建立树
        root.left=self.reconstructiontree(pre[1:i+1],med[:i])#左侧树
        root.right=self.reconstructiontree(pre[i+1:],med[i+1:])#右侧数
        return root
    
def main():
    pre=[1,2,4,7,3,5,6,8]
    med=[4,7,2,1,5,3,8,6]
    test=solution()
    root=test.reconstructiontree(pre,med)
    print (root)
     
if __name__=='__main__':
    main()

程序的输出结果为一个树类型,也可以根据后序遍历,来自行修改程序代码

题6--队列和栈

  • 队列的特点是先进先出
  • 栈的特点是先进后出
题干基本意思就是用两个栈实现队列的功能---即利用先进后出的两个数据结构实现一个先进先出的数据结构

关于解题思路的逻辑,书中介绍的很清楚 mark


image.png image.png
image.png

下面为程序代码:

"""
栈:先进后出,要出的元素一定在栈顶,其实列表的pop方法就是此原理
队列:先进的先出
"""
class queue(object):
    def __init__(self):
        self.stack1=[]
        self.stack2=[]#声明了两个栈
    def push(self,a):#加入元素
        self.stack1.append(a)#利用append加入元素
        #print (self.stack1)
    def pop(self):
        if len(self.stack1)==0 and len(self.stack2)==0:
            return None
        elif len(self.stack2)==0:
            while len(self.stack1)>0:
                self.stack2.append(self.stack1.pop())#栈2接受栈1的弹出元素,这时候在栈1中先进的元素,在栈2中变成了后进元素,即弹出时顺序优先
        return self.stack2.pop()


def main():
    q=queue()#实例化
    q.push(1)
    q.push(2)
    q.push(3)
    #print (q.stack1)
    print (q.pop())
    print (q.pop())
    print (q.pop())
if __name__=='__main__':
    main()
  • 只有思路清晰,才能做好事,否则只能越做越糊涂,写代码如此,生活更应如此,想清楚的话再说出口,想清楚的事情再做,于人于己都好。

相关文章

  • 剑指offer--algorithm3

    归零后才能重新出发,不留遗憾才是最好的故事。 本节的两题实际上介绍了两种重要且常见的数据结构,一个为树,一个为栈和...

  • 剑指

    遥望中原九点烟,风云直上七重天。 今朝再向江湖去,一剑流星谁比肩? 2011.10(1488)

  • 剑指

    1. 二维数组中查找 在一个二维数组中(每个一维数组的长度相同),每一行都按照从左到右递增的顺序排序,每一列都按照...

  • 全网最全剑指offer题目解答

    【剑指offer】Java版代码(完整版) 【剑指offer】1-10题 【剑指offer】11-20题 【剑指o...

  • 剑指offer

    第一题:在一个二维数组中,每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请完成一个函数,...

  • 剑指BAT

    Android工作5年半了,一毕业就开始做这行。在现在这家公司工作了3年整,最近有换工作的打算,所以在猎聘...

  • 《剑指offer》

    4.调整数组顺序使奇数位于偶数前面 题目描述:输入一个整数数组,实现一个函数来调整该数组中数字的顺序,使得所有的奇...

  • 气剑指

    “聚气于指尖,凝其成剑,利可断金。”牢头对身边的狱卒说。 只见牢头举起的右手指尖逐渐变红,转而变白,隐隐发出音量很...

  • 剑指offer

    二维数组中查找数在一个二维数组中(每个一维数组的长度相同),每一行都按照从左到右递增的顺序排序,每一列都按照从上到...

  • 剑指苍穹

    逆天命,斩苍穹,吾乃修士,率性而为!《剑指苍穹》是一款逍遥仙侠MMORPG——群魔阻道,斩群魔;妖邪拦路,诛妖邪,...

网友评论

      本文标题:剑指offer--algorithm3

      本文链接:https://www.haomeiwen.com/subject/iweplftx.html