歸零后才能重新出發(fā)，不留遺憾才是最好的故事。

• 本節(jié)的兩題實(shí)際上介紹了兩種重要且常見的數(shù)據(jù)結(jié)構(gòu)，一個(gè)為樹，一個(gè)為棧和隊(duì)列

題 5 --重建二叉樹

關(guān)于樹的考察，書中有這樣的描述，一般指的為二叉樹--每一個(gè)節(jié)點(diǎn)都有兩個(gè)子節(jié)點(diǎn)，而考察二叉樹，一般考察的為遍歷 。關(guān)于樹的題目多變，但是一般解決方法都是通過前序遍歷、中序遍歷、后序遍歷等遍歷思路，而每一種思路都有遞歸跟循環(huán)兩種方法。

image.png

image.png

image.png

程序代碼如下：

class treenode(object):#定義一個(gè)樹的節(jié)點(diǎn)
    def __init__(self,a):
        self.value=a
        self.left=None#定義左節(jié)點(diǎn)
        self.right=None#定義右節(jié)點(diǎn)

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])#確定根節(jié)點(diǎn)的位置
        root=treenode(pre[0])#建立樹
        root.left=self.reconstructiontree(pre[1:i+1],med[:i])#左側(cè)樹
        root.right=self.reconstructiontree(pre[i+1:],med[i+1:])#右側(cè)數(shù)
        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()

程序的輸出結(jié)果為一個(gè)樹類型，也可以根據(jù)后序遍歷，來自行修改程序代碼

題6--隊(duì)列和棧

• 隊(duì)列的特點(diǎn)是先進(jìn)先出
• 棧的特點(diǎn)是先進(jìn)后出

題干基本意思就是用兩個(gè)棧實(shí)現(xiàn)隊(duì)列的功能---即利用先進(jìn)后出的兩個(gè)數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)一個(gè)先進(jìn)先出的數(shù)據(jù)結(jié)構(gòu)

關(guān)于解題思路的邏輯，書中介紹的很清楚 mark

image.png

image.png

image.png

下面為程序代碼：

"""
棧：先進(jìn)后出，要出的元素一定在棧頂,其實(shí)列表的pop方法就是此原理
隊(duì)列：先進(jìn)的先出
"""
class queue(object):
    def __init__(self):
        self.stack1=[]
        self.stack2=[]#聲明了兩個(gè)棧
    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的彈出元素，這時(shí)候在棧1中先進(jìn)的元素，在棧2中變成了后進(jìn)元素，即彈出時(shí)順序優(yōu)先
        return self.stack2.pop()


def main():
    q=queue()#實(shí)例化
    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()

• 只有思路清晰，才能做好事，否則只能越做越糊涂，寫代碼如此，生活更應(yīng)如此，想清楚的話再說出口，想清楚的事情再做，于人于己都好。