Python程序員面試分類真題5

Python程序員面試分類真題5(總分：100.00，做題時間：90分鐘)面試題(總題數：7，分數：100.00)1.

如何把一個有序整數數組放到二叉樹中

（分數：14.00）__________________________________________________________________________________________

正確答案：(如果要把一個有序的整數數組放到二叉樹中，那么所構造出來的二叉樹必定也是一棵有序的二叉樹。鑒于此，實現(xiàn)思路為：取數組的中間元素作為根結點，將數組分成左右兩部分，對數組的兩部分用遞歸的方法分別構建左右子樹。如下圖所示。

如上圖所示，首先取數組的中間結點6作為二叉樹的根結點，把數組分成左右兩部分，然后對于數組的左右兩部分子數組分別運用同樣的方法進行二叉樹的構建，例如，對于左半部分子數組，取中間結點3作為樹的根結點，再把子數組分成左右兩部分。依此類推，就可以完成二叉樹的構建，實現(xiàn)代碼如下：

classBiTNode:

def__init__(self):

self.data=None

self.lchild=None

self.rchild=None

#方法功能:把有序數組轉換為二叉樹

defarrayotree(arr,start,end):

root=None

ifend＞=start:

root=BiTNode()

mid=(start+end+1)/2

#樹的根結點為數組中間的元素

root.data=arr[mid]

#遞歸的用左半部分數組構造root的左子樹

root.lchild=arraytotree(arr,start,mid-1)

#遞歸的用右半部分數組構造root的右予樹

root.rchild=arraytotree(arr,mid+1,end)

else:

root=None

returnroot

#用中序遍歷的方式打印出二叉樹結點的內容

defprintTreeMidOrder(root):

ifroot==None:

return

#歷root結點的左子樹

ifroot.lchild!=None:

printTreeMidOrder(root.lchild)

#遍歷root結點

printroot.data,

#遍歷root結點的右子樹

ifroot.rchild!=None:

printTreeMidOrder(root.rchild)

if__name__=="__main__":

arr=[1,2,3,4,5,6,7,8,9,10]

print"數組:",

i=0

whilei＜len(arr):

printarr[i],

i+=1

print'\n'

root=arraytotree(arr,0,len(arr)-1)

print"轉換成樹的中序遍歷為:",

printTreeMidOrder(root)

print'\n'

程序的運行結果為：

數組：12345678910

轉換成樹的中序遍歷為：12345678910

算法性能分析：

由于這種方法只遍歷了一次數組，因此，算法的時間復雜度為O(N)，其中，N表示的是數組長度。)解析：[考點]如何把一個有序整數數組放到二叉樹中2.

給定一棵二叉樹，要求逐層打印二叉樹結點的數據，例如有如下二叉樹：

對這棵二叉樹層序遍歷的結果為1，2，3，4，5，6，7。

（分數：14.00）__________________________________________________________________________________________

正確答案：(為了實現(xiàn)對二叉樹的層序遍歷，就要求在遍歷一個結點的同時記錄下它的孩子結點的信息，然后按照這個記錄的順序來訪問結點的數據，在實現(xiàn)的時候可以采用隊列來存儲當前遍歷到的結點的孩子結點，從而實現(xiàn)二叉樹的層序遍歷，遍歷過程如下圖所示。

在上圖中，圖(1)首先把根結點1放到隊列里面，然后開始遍歷。圖(2)隊列首元素(結點1)出隊列，同時它的孩子結點2和結點3進隊列；圖(3)接著出隊列的結點為2，同時把它的孩子結點4和結點5放到隊列里，依此類推就可以實現(xiàn)對二叉樹的層序遍歷。

實現(xiàn)代碼如下：

fromcollectionsimportdeque

classBiTNode:

def__init__(self):

self.data=None

self.lchild=None

self.rchild=None

#方法功能:把有序數組轉換為二叉樹

defarraytotree(arr,start,end):

roo=None

ifend＞=start:

root=BiTNode();

mid=(start+end+1)/2;

#樹的根結點為數組中間的元素

root.data=arr[mid];

#遞歸的用左半部分數組構造root的左子樹

root.lchild=arraytotree(arr,start,mid-1);

#遞歸的用右半部分數組構造root的右子樹

root.rchild=arraytotree(arr,mid+1,end);

else:

root=None

returnroot

"""

方法功能:用層序遍歷的方式打印出二叉樹結點的內容

輸入參數:root:二叉樹根結點

"""

defprintTreeLayer(root):

ifroot==None:

return;

queue=deque()

#樹根結點進隊列

queue.append(root)

whilelen(queue)＞0:

p=queue,popleft()

#訪問當前結點

print(p.data),

#如果這個結點的左孩子不為空則入隊列

ifp.lchild!=None:

queue.append(p.lchild)

#如果這個結點的右孩子不為空則入隊列

ifp.rchild!=None:

queue.append(p.rchild);

if__name__=="__main__":

arr=[1,2,3,4,5,6,7,8,9,10]

root=arraytotree(arr,0,len(arr)-1);

print"樹的層序遍歷結果為:",

printTreeLaver(root);

程序的運行結果為：

樹的層序遍歷結果為：63925810147

算法性能分析：

在二叉樹的層序遍歷過程中，對樹中的各個結點只進行了一次訪問，因此，時間復雜度為O(N)，此外，這種方法還使用了隊列來保存遍歷的中間結點，所使用隊列的大小取決于二叉樹中每一層中結點個數的最大值。具有N個結點的完全二叉樹的深度為h=log2N+1。而深度為h的這一層最多的結點個數為2h-1=n/2。也就是說隊列中可能的最多的結點個數為N/2。因此，這種算法的空間復雜度為O(N)。)解析：[考點]如何從頂部開始逐層打印二叉樹結點數據3.

給定一棵二叉樹，它的每個結點都是正整數或負整數，如何找到一棵子樹，使得它所有結點的和最大?

（分數：14.00）__________________________________________________________________________________________

正確答案：(要求一棵二叉樹的最大子樹和，最容易想到的辦法就是針對每棵子樹，求出這棵子樹中所有結點的和，然后從中找出最大值。恰好二叉樹的后序遍歷就能做到這一點。在對二叉樹進行后序遍歷的過程中，如果當前遍歷的結點的值與其左右子樹和的值相加的結果大于最大值，則更新最大值。如下圖所示：

在上面這個圖中，首先遍歷結點-1，這個子樹的最大值為-1，同理，當遍歷到結點9時，子樹的最大值為9，當遍歷到結點3的時候，這個結點與其左右孩子結點值的和(3-1+9=11)大于最大值(9)。因此，此時最大的子樹為以3為根結點的子樹，依此類推，直到遍歷完整棵樹為止。實現(xiàn)代碼如下：

classBiTNode:

def__init__(self):

self.data=None

self.lchild=None

self.rchild=None

classTest:

def__init__(self):

self.maxSum=-2**31

"""

方法功能:求最大子樹

輸入參數:root:根結點;

maxRoot最大子樹的根結點

返回值:以root為根結點子樹所有結點的和

"""

deffindMaxSubTree(self,root,maxRoot):

ifroot==None:

return0

#求root左子樹所有結點的和

1max=self.findMaxSubTree(root.lchild,maxRoot)

#求root右子樹所有結點的和

rmax=self.findMaxSubTree(root.rchild,maxRoot)

sums=1max+rmax+root.data

#以root為根的子樹的和大于前面求出的最大值

ifsums＞self.maxSum:

self.maxSum=sums

maxRoot.data=root.data

#返回以root為根結點的予樹的所有結點的和

returnsums

"""

方法功能:構造二叉樹

返回值:返回新構造的二叉樹的根結點

"""

defconstructTree(self):

root=BiTNode()

node1=BiTNode()

node2=BiTNode()

node3=BiTNode()

node4=BiTNode()

root.data=6

node1.data=3

node2.data=-7

node3.data=-1

node4.data=9

root.lchild=node1

root.rchild=node2

node1.lchild=node3

node1.rchild=node4

node2.lchild=node2.rchild=node3.lchild=node3.rchild=\

node4.lchild=node4.rchild=None

returnroot

if__name__=="__main__":

#構造二叉樹

test=Test()

root=test.constructTree()

maxRoot=BiTNode()#最大子樹的根結點

test.findMaxSubTree(root,maxRoot)

print"最大子樹和為:"+str(test.maxSum)

print"對應子捌的根結點為:"+str(maxRoot.data)

程序的運行結果為：

最大子樹和為：11

對應子樹的根結點為：3

算法性能分析：

這種方法與二叉樹的后序遍歷有相同的時間復雜度，即為O(N)，其中，N為二叉樹的結點個數。)解析：[考點]如何求一棵二叉樹的最大子樹和4.

兩棵二叉樹相等是指這兩棵二叉樹有著相同的結構，并且在相同位置上的結點有相同的值。如何判斷兩棵二叉樹是否相等?

（分數：14.00）__________________________________________________________________________________________

正確答案：(如果兩棵二叉樹root1、root2相等，那么root1與root2結點的值相同，同時它們的左右孩子也有著相同的結構，并且對應位置上結點的值相等，即root1.data=root2.data，并且root1的左子樹與root2的左子樹相等，root1的右子樹與root2的右子樹相等。根據這個條件，可以非常容易地寫出判斷兩棵二叉樹是否相等的遞歸算法。實現(xiàn)代碼如下：

classBiTNode:

def__init__(self):

self.data=None

self.lchild=None

self.rcbild=None

"""

方法功能:判斷兩棵二叉樹是否相等

參數:root1與root2分別為兩棵二叉樹的根結點

返回值:true:如果兩棵樹相等則返回true,否則返回false

"""

defisEqual(root1,root2):

ifroot1==Noneandroot2==None:

returnTrue

ifroot1==Noneandroot2!=None:

returnFalse

ifroot1!=Noneandroot2==None:

returnFalse

ifroot1.data==root2.data:

returnisEqual(root1.lchild,root2.lchild)andisEqual(root1.rchild,root2.rchild)

else:

returnFalse

defconstructTree():

root=BiTNode()

node1=BiTNode()

node2=BiTNode()

node3=BiTNode()

node4=BiTNode()

root.data=6

node1.data=3

node2.data=-7

node3.data=-1

node4.data=9

root.lchild=node1

root.rchild=node2

nodel.lchild=node3

nodel.rchild=node4

node2.lchild=node2.rchild=node3.lchild=node3.rchild=\

node4.lchild=node4.rchild=None

returnroot

if__name__=="__main__":

root1=constructTree()

root2=constructTree()

equal=isEqual(root1,root2)

ifequal:

print"這兩棵樹相等"

else:

print"這兩棵樹不相等"

程序的運行結果為：

這兩棵樹相等

算法性能分析：

這種方法對兩棵樹只進行了一次遍歷，因此，時間復雜度為O(N)。此外，這種方法沒有申請額外的存儲空間。)解析：[考點]如何判斷兩棵二叉樹是否相等5.

輸入一棵二元查找樹，將該二元查找樹轉換成一個排序的雙向鏈表。要求不能創(chuàng)建任何新的結點，只能調整結點的指向。例如：

（分數：14.00）__________________________________________________________________________________________

正確答案：(由于轉換后的雙向鏈表中結點的順序與二叉樹的中序遍歷的順序相同，因此，可以對二叉樹的中序遍歷算法進行修改，通過在中序遍歷的過程中修改結點的指向來轉換成一個排序的雙向鏈表。實現(xiàn)思路如下圖所示：假設當前遍歷的結點為root，root的左子樹已經被轉換為雙向鏈表(如下圖(1)所示)，使用兩個變量pHead與pEnd分別指向鏈表的頭結點與尾結點。那么在遍歷root結點的時候，只需要將root結點的lchild(左)指向pEnd，把pEnd的rchild(右)指向root；此時root結點就被加入到雙向鏈表里了，因此，root變成了雙向鏈表的尾結點。對于所有的結點都可以通過同樣的方法來修改結點的指向。因此，可以采用遞歸的方法來求解，在求解的時候需要特別注意遞歸的結束條件以及邊界情況(例如雙向鏈表為空的時候)。

實現(xiàn)代碼如下：

classBiTNode:

def__init__(self):

self.data=None

self.lchild=None

self.rchild=None

classTest:

def__init__(self):

self.pHead=None#雙向鏈表頭結點

self.pEnd=None#雙向鏈表尾結點

#方法功能:把有序數組轉換為二叉樹

defarraytotree(self,arr,start,end):

root=None

ifend＞=start:

root=BiTNode()

mid=(start+end+1)/2

#樹的根結點為數組中間的元素

root.data=arr[mid]

#遞歸的用左半部分數組構造root的左子樹

root.lchild=self.arraytotree(arr,start,mid-1)

#遞歸的用右半部分數組構造root的右子樹

root.rchild=self.arraytotree(arr,mid+1,end)

else:

root=None

returnroot

"""

方法功能:把二叉樹轉換為雙向列表

輸入參數:root:二叉樹根結點

"""

definOrderBSTree(self,root):

ifroot==None:

return

#轉換root的左子樹

self.inOrderBSTree(root.lchild)

root,lchild=self.pEnd#使當前結點的左孩子指向雙向鏈表中最后一個結點

ifNone==self.pEnd:#雙向列表為空,當前遍歷的結點為雙向鏈表的頭結點

self.pHead=root

else:#使雙向鏈表中最后一個結點的右孩子指向當前結點

self.pEnd.rchild=root

self.pEnd=root#將當前結點設為雙向鏈表中最后一個結點

#轉換root的右予樹

self.inOrderBSTree(root.rchild)

if__name__=="__main__":

arr=[1,2,3,4,5,6,7]

test=Test()

root=test.arraytotree(arr,O,len(arr)-1)

test.inOrderBSTree(root)

print"轉換后雙向鏈表正向遍歷:",

#cur=BiTNode()

cur=test.pHead

whilecur!=None:

printcur.data,

cur=cur.rchild

print'\n'

print"轉換后雙向鏈表逆向遍歷:",

cur=test.pEnd

whilecur!=None:

printcur.data,

cur=cur.lchild

程序的運行結果為：

轉換后雙向鏈表正向遍歷：1234567

轉換后雙向鏈表逆向遍歷：7654321

算法性能分析：

這種方法與二叉樹的中序遍歷有著相同的時間復雜度O(N)。此外，這種方法只用了兩個額外的變量pHead與pEnd來記錄雙向鏈表的首尾結點，因此，空間復雜度為O(1)。)解析：[考點]如何把二叉樹轉換為雙向鏈表6.

輸入一個整數數組，判斷該數組是否是某二元查找樹的后序遍歷的結果。如果是，那么返回true，否則返回false。例如數組[1，3，2，5，7，6，4]就是下圖中二叉樹的后序遍歷序列。

（分數：14.00）__________________________________________________________________________________________

正確答案：(二元查找樹的特點是：對于任意一個結點，它的左子樹上所有結點的值都小于這個結點的值，它的右子樹上所有結點的值都大于這個結點的值。根據它的這個特點以及二元查找樹后序遍歷的特點，可以看出，這個序列的最后一個元素一定是樹的根結點(上圖中的結點4)，然后在數組中找到第一個大于根結點4的值5，那么結點5之前的序列(1，3，2)對應的結點一定位于結點4的左子樹上，結點5(包含這個結點)后面的序列一定位于結點4的右子樹上(也就是說結點5后面的所有值都應該大于或等于4)。對于結點4的左子樹遍歷的序列{1，3，2}以及右子樹的遍歷序列{5，7，6}可以采用同樣的方法來分析，因此，可以通過遞歸方法來實現(xiàn)，實現(xiàn)代碼如下：

"""

方法功能:判斷一個數組是否是二元查找樹的后續(xù)遍歷序列

輸入參數:arr:數組:

返回值:true:是,否則返回false

"""

defIsAfterOrder(arr,start,end):

ifarr==None:

returnFalse

#數組的最后一個結點必定是根結點

root=arr[end]

#找到第一個大于root的值,那么前面所有的結點都位于root的左子樹上

i=start

whilei＜end:

if(arr[i]＞root):

break

i+=1

#如果序列是后續(xù)遍歷的序列,那么從i開始的所有值都應該大于根結點root的值

j=i

whilej＜end:

ifarr[j]＜root:

returnFalse

j+=1

left_IsAfterOrder=True

right_IsAfterOrder=True

#判斷小于root值的序列是否是某一二元查找樹的后續(xù)遍歷

ifi＞start:

left_IsAfierOrder=IsAfterOrder(arr,start,i-1)

#判斷大于root值的序列是否是某一二元查找樹的后續(xù)遍歷

ifj＜end:

right_IsAfterOrder=IsAfterOrder(arr,i,end)

returnleft_IsAfterOrderandright_IsAfterOrder

if__name__="__main__":

arr=[1,3,2,5,7,6,4]

result=IsAfterOrder(arr,0,len(arr)-1)

i=0

whilei＜len(arr):

printarr[i],

i+-=1

ifresult:

print"是某一二元查找樹的后續(xù)遍歷序列"

else:

print"不是某一二元查找樹的后續(xù)遍歷序列"

程序的運行結果為：

1325764是某一二元查找樹的后序遍歷序列

算法性能分析：

這種方法對數組只進行了一次遍歷，因此，時間復雜度O(N)。)解析：[考點]如何判斷一個數組是否是二元查找樹后序遍歷的序列7.

對于一棵給定的排序二叉樹，求兩個結點的共同父結點，例如在下圖中，結點1和結點5的共同父結點為3。

（分數：16.00）__________________________________________________________________________________________

正確答案：(方法一：路徑對比法

對于一棵二叉樹的兩個結點，如果知道了從根結點到這兩個結點的路徑，就可以很容易地找出它們最近的公共父結點。因此，可以首先分別找出從根結點到這兩個結點的路徑(例如上圖中從根結點到結點1的路徑為6-＞3-＞2-＞1，從根結點到結點5的路徑為6-＞3-＞5)；然后遍歷這兩條路徑，只要是相等的結點都是它們的父結點，找到最后一個相等的結點即為離它們最近的共同父結點，在這個例子中，結點3就是它們共同的父結點。示例代碼如下：

classBiTNode:

def__init__(self):

self.data=None

self.lchild=None

self.rchild=None

classstack:

#模擬棧

def__init__(self):

self.items=[]

#判斷棧是否為空

defisEmpty(self):

returnlen(self.items)==0

#返回棧的大小

defsize(self):

returnlen(self.items)

#返回棧頂元素

defpeek(self):

ifnotself.isEmpty():

returnself.items[len(self.items)-1]

else:

returnNone

#彈棧

defpop(self):

iflen(self.items)＞0:

returnself.items.pop()

else:

print"棧已經為空"

returnNone

#壓棧

defpush(self,item):

self.items.append(item)

"""

方法功能:獲取二叉樹從根結點root到node結點的路徑

輸入參數:root:根結點;node:二叉樹中的某個結點;s:用來存儲路徑的棧返回值:node在root的予樹上,或node==root時返回true,否則返回false

"""

defgetPathFromRoot(root,node,s):

ifroot==None:

returnFalse

ifroot==node:

s.push(root)

returnTrue

"""

如果node結點在root結點的左予樹或右子樹上,

那么root就是node的祖先結點,把它加到棧里

"""

ifgetPathFromRoot(root.lchild,node,s)orgetPathFromRoot(root.rchild,node,s):

s.push(root)

returnTrue

returnFalse

"""

方法功能:查找二叉樹中兩個結點最近的共同父結點

輸入參數:root:根結點;node1與node2為二叉樹中兩個結點

返回值:node1與node2最近的共同父結點

"""

defFindParentNode(root,node1,node2):

stack1=stack()#保存從root到node1的路徑

stack2=stack()#保存從root到node2的路徑

#獲取從root到node1的路徑

getPathFromRoot(root,node1,stack1)

#獲取從root到node2的路徑

getPathFromRoot(root,node2,stack2)

commonParent=None

#獲取最靠近node1和node2的父結點

whilestackl.peek()==stack2.peek():

commonParent=stack1.peek()

stack1.pop()

stack2.pop()

returncommonParent

if__name__=="__main__":

arr=[1,2,3,4,5,6,7,8,9,10]

root=arraytotree(arr,0,len(arr)-1)

node1=root.lchild.lchild.lchild

node2=root.lchild.rchild

res=None

res=FindParentNode(root,node1,node2)

ifres!=None:

printstr(node1.data)+"與"+str(node2.data)+"的最近公共父結點為:"+str(res.data),

else:

print"沒有公共父結點"

程序的運行結果為：

1與5的最近公共父結點為：3

算法性能分析：

當獲取二叉樹從根結點root到node結點的路徑時，最壞的情況就是把樹中所有結點都遍歷了一遍，這個操作的時間復雜度為O(N)，再分別找出從根結點到兩個結點的路徑后，找它們最近的公共父結點的時間復雜度也為O(N)，因此，這種方法的時間復雜度為O(N)。此外，這種方法用棧保存了從根結點到特定結點的路徑，在最壞的情況下，這個路徑包含了樹中所有的結點，因此，空間復雜度也為O(N)。

很顯然，這種方法還不夠理想。下面介紹另外一種能降低空間復雜度的方法。

方法二：結點編號法

根據性質，可以把二叉樹看成是一棵完全二叉樹(不管實際的二叉樹是否為完全二叉樹，二叉樹中的結點都可以按照完全二叉樹中對結點編號的方式進行編號)，下圖為對二叉樹中的結點按照完全二叉樹中結點的編號方式進行編號后的結果，結點右邊的數字為其對應的編號。

根據性質可以知道，一個編號為n的結點，它的父親結點的編號為n/2。假如要求node1與node2的最近的共同父結點，首先把這棵樹看成是一棵完全二叉樹(不管結點是否存在)，分別求得這兩個結點的編號n1，n2。然后每次找出n1與n2中較大的值除以2，直到n1==n2為止，此時n1或n2的值對應結點的編號就是它們最近的共同父結點的編號，接著可以根據這個編號信息找到對應的結點，具體方法為：通過觀察二叉樹中結點的編號可以發(fā)現(xiàn)：首先把根結點root看成1，求root的左孩子編號的方法為把root對應的編號看成二進制，然后向左移一位，末尾補0，如果是root的右孩子，那么末尾補1，因此，通過結點位置的二進制碼就可以確定這個結點。例如結點3的編號為2(二進制10)，它的左孩子的求解方法為：10，向左移一位末尾補0，可以得到二進制100(十進制4)，位置為4的結點的值為2。從這個特性可以得出通過結點位置信息獲取結點的方法，例如要求位置4的結點，4的二進制碼為100，由于1代表根結點，接下來的一個0代表是左子樹root.lcluld，最后一個0也表示左子樹root.lchild.lchild，通過這種方法非常容易根據結點的編號找到對應的結點。實現(xiàn)代碼如下：

importmath

classBiTNode:

def__init__(self):

self.data=None

self.lchild=None

self.rchild=None

#方法功能:把有序數組轉換為二叉樹

defarraytotree(arr,start,end):

root=None

ifend＞=start:

root=BiTNode()

mid=(start+end+1)/2

#樹的根結點為數組中問的元素

root.data=arr[mid]

#遞歸的用左半部分數組構造root的左子樹

root.lchild=arraytotree(arr,start,mid-1)

#遞歸的用右半部分數組構造root的右予樹

root.rchild=arraytotree(arr,mid+1,end)

else:

root=None

returnroot

classIntRef:

def__init__(self):

self.num=None

"""

方法功能:找出結點在二叉樹中的編號

輸入參數:root:根結點node:待查找結點;number:node結點在二叉樹中的編號

返回值:true:找到該結點的位置,否則返回false

"""

defgetNo(root,node,number):

ifroot==None:

returnFalse

ifroot==node:

returnTrue

tmp=number.num

number.num=2*tmp

#node結點在root的左子樹中,左子樹編號為當前結點編號的2倍

ifgetNo(root.lchild,node,number):

returnTrue

#node結點在root的右子樹中,右子樹編號為當前結點編號的2倍加1

else:

number.num=tmp*2+1

returngetNo(root.rchild,node,number)

"""

方法功能:根據結點的編號找出對應的結點

輸入參數:root:根結點;number為結點的編號

返回值:編號為number對應的結點

"""

defgetNodeFromNum(root,number):

ifroot==Noneornumber＜0:

returnNone

ifnumber=1:

returnroot

#結點編號對應二進制的位數(最高位一定為1,因為根結點代表1)

lens=int((math.log(number)/math.log(2)))

#去掉根結點表示的1

number-=1＜＜lens

whilelens＞0:

#如果這一位二進制的值為1,

#那么編號為number的結點必定在當前結點的右子樹上

if(1＜＜(lens-1))&number==1:

root=root.rchild

else:

root=root.lchild

lens-=1

returnroot

"""