Python程序員面試分類真題6(總分：100.00，做題時間：90分鐘)面試題(總題數(shù)：6，分?jǐn)?shù)：100.00)1.

給定一個二叉樹根結(jié)點(diǎn)，復(fù)制該樹，返回新建樹的根結(jié)點(diǎn)。

（分?jǐn)?shù)：16.50）__________________________________________________________________________________________

正確答案：(用給定的二叉樹的根結(jié)點(diǎn)root來構(gòu)造新的二叉樹的方法為：首先創(chuàng)建新的結(jié)點(diǎn)dupTree，然后根據(jù)root結(jié)點(diǎn)來構(gòu)造dupTree結(jié)點(diǎn)(dupTree.data=root.data)，最后分別用root的左右子樹來構(gòu)造dupTree的左右子樹。根據(jù)這個思路可以實(shí)現(xiàn)二叉樹的復(fù)制，使用遞歸方式實(shí)現(xiàn)的代碼如下：

classBiTNode:

def__init__(self):

self.data=None

self.lchild=None

self.rchild=None

defcreateDupTree(root):

ifroot==None:

returnNone

#二叉樹根結(jié)點(diǎn)

dupTree=BiTNode()

dupTree.data=root.data

#復(fù)制左予樹

dupTree.lchild=createDupTree(root.lchild)

#復(fù)制右予樹

dupTree.rchild=createDupTree(root.rchild)

returndupTree

defprintTreeMidOrder(root):

ifroot==None:

return

#遍歷root結(jié)點(diǎn)的左予樹

ifroot.lchild!=None:

printTreeMidOrder(root.lchild)

#遍歷root結(jié)點(diǎn)

printroot.data,

#遍歷root結(jié)點(diǎn)的右子樹

ifroot.rchild!=None:

printTreeMidOrder(root.rchild)

if__name__=="__main__":

root1=constructTree()

root2=createDupTree(root1)

print"原始二叉樹中序遍歷:",

printTreeMidOrder(root1)

print'\n'

print"新的二叉樹中序遍歷:",

printTreeMidOrder(root2)

程序的運(yùn)行結(jié)果為：

原始二叉樹中序遍歷：-1396-7

新的二叉樹中序遍歷：-1396-7

算法性能分析：

這種方法對給定的二叉樹進(jìn)行了一次遍歷，因此，時間復(fù)雜度為O(N)，此外，這種方法需要申請N個額外的存儲空間來存儲新的二叉樹。)解析：[考點(diǎn)]如何復(fù)制二叉樹2.

從樹的根結(jié)點(diǎn)開始往下訪問一直到葉子結(jié)點(diǎn)經(jīng)過的所有結(jié)點(diǎn)形成一條路徑。找出所有的這些路徑，使其滿足這條路徑上所有結(jié)點(diǎn)數(shù)據(jù)的和等于給定的整數(shù)。例如：給定如下二叉樹與整數(shù)8，滿足條件的路徑為6-＞3-＞-1(6+3-1=8)。

（分?jǐn)?shù)：16.50）__________________________________________________________________________________________

正確答案：(可以通過對二叉樹的遍歷找出所有的路徑，然后判斷各條路徑上所有結(jié)點(diǎn)的值的和是否與給定的整數(shù)相等，如果相等，則打印出這條路徑。具體實(shí)現(xiàn)方法可以通過對二叉樹進(jìn)行先序遍歷來實(shí)現(xiàn)，實(shí)現(xiàn)思路為：對二叉樹進(jìn)行先序遍歷，把遍歷的路徑記錄下來，當(dāng)遍歷到葉子結(jié)點(diǎn)時，判斷當(dāng)前的路徑上所有結(jié)點(diǎn)數(shù)據(jù)的和是否等于給定的整數(shù)，如果相等則輸出路徑信息，示例代碼如下：

classBiTNode:

def__init__(self):

self.data=None

self.lchild=None

self.rchild=None

"""

方法功能:打印出滿足所有結(jié)點(diǎn)數(shù)據(jù)的和等于num的所有路徑

參數(shù):root:二叉樹根結(jié)點(diǎn);num:給定的整數(shù);sum:當(dāng)前路徑上所有結(jié)點(diǎn)的和

用來存儲從根結(jié)點(diǎn)到當(dāng)前遍歷到結(jié)點(diǎn)的路徑

"""

defFindRoad(root,num,sums,v):

#記錄當(dāng)前遍歷的root結(jié)點(diǎn)

sums+=root.data

v.append(root.data)

#當(dāng)前結(jié)點(diǎn)是葉子結(jié)點(diǎn)且遍歷的路徑上所有結(jié)點(diǎn)的和等于num

ifroot.lchild==Noneandroot.rchild==Noneandsums==num:

i=0

whilei＜len(v):

printv[i],

i+=1

print'\n'

#遍歷root的左子樹

ifroot.lchild!=None:

FindRoad(root.lchild,num,sums,v)

#遍歷root的右予樹

ifroot.rchild!=None:

FindRoad(root.rchild,num,sums,v)

#清除遍歷的路徑

sums-=v[-1]

v.remove(v[-1])

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__":

root=constructTree()

s=[]

print"滿足路徑結(jié)點(diǎn)和等于8的路徑為:",

FindRoad(root,8,0,s)

程序的運(yùn)行結(jié)果為：

滿足路徑結(jié)點(diǎn)和等于8的路徑為：63-1

算法性能分析：

這種方法與二叉樹的先序遍歷有著相同的時間復(fù)雜度O(N)，此外，這種方法用一個數(shù)組存放遍歷路徑上結(jié)點(diǎn)的值，在最壞的情況下時間復(fù)雜度為O(N)(所有結(jié)點(diǎn)只有左子樹，或所有結(jié)點(diǎn)只有右子樹)，因此，空間復(fù)雜度為O(N)。)解析：[考點(diǎn)]如何在二叉樹中找出與輸入整數(shù)相等的所有路徑3.

二叉樹的鏡像就是二叉樹對稱的二叉樹，就是交換每一個非葉子結(jié)點(diǎn)的左子樹指針和右子樹指針，如下圖所示，請寫出能實(shí)現(xiàn)該功能的代碼。注意：請勿對該樹做任何假設(shè)，它不一定是平衡樹，也不一定有序。

（分?jǐn)?shù)：16.50）__________________________________________________________________________________________

正確答案：(從上圖可以看出，要實(shí)現(xiàn)二叉樹的鏡像反轉(zhuǎn)，只需交換二叉樹中所有結(jié)點(diǎn)的左右孩子即可。由于對所有的結(jié)點(diǎn)都做了同樣的操作，因此，可以用遞歸的方法來實(shí)現(xiàn)，由于需要調(diào)用printTreeLayer層序打印二叉樹，這種方法中使用了隊(duì)列來實(shí)現(xiàn)，實(shí)現(xiàn)代碼如下：

fromcollectionsimportdeque

classBiTNode:

def__init__(self):

self.data=None

self.lchild=None

self.rchild=None

#對二叉樹進(jìn)行鏡像反轉(zhuǎn)

defreverseTree(root):

ifroot==None:

return

reverseTree(root.lchild)

reverseTree(root.rchild)

tmp=root.lchild

root.lchild=root.rchild

root.rchild=tmp

defarraytotree(arr,start,end):

root=None

ifend＞=start:

root=BiTNode()

mid=(start+end+1)/2

#樹的根結(jié)點(diǎn)為數(shù)組中間的元素

root.data=arr[mid]

#遞歸的用左半部分?jǐn)?shù)組構(gòu)造root的左子樹

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

#遞歸的用右半部分?jǐn)?shù)組構(gòu)造root的右子樹

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

else:

root=None

returnroot

defprintTreeLayer(root):

ifroot==None:

return

queue=deque()

#樹根結(jié)點(diǎn)進(jìn)隊(duì)列

queue.append(root)

whilelen(queue)＞0:

p=queue.popleft()

#訪問當(dāng)前結(jié)點(diǎn)

printp.data,

#如果這個結(jié)點(diǎn)的左孩子不為空則入隊(duì)列

ifp.lchild!=None:

queue.append(p.lchild)

#如果這個結(jié)點(diǎn)的右孩子不為空則入隊(duì)列

ifp.rchild!=None:

queue.append(p.rchild)

if__name__=="__main__":

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

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

print"二叉樹層序遍歷結(jié)果為:",

printTreeLayer(root)

print'\n'

reverseTree(root)

print"反轉(zhuǎn)后的二叉樹層序遍歷結(jié)果為:",

printTreeLayer(root)

程序的運(yùn)行結(jié)果為：

二叉樹層序遍歷結(jié)果為：4261357

反轉(zhuǎn)后的二叉樹層序遍歷結(jié)果為：4627531

算法性能分析：

由于對給定的二叉樹進(jìn)行了一次遍歷，因此，時間復(fù)雜度為O(N)。)解析：[考點(diǎn)]如何對二叉樹進(jìn)行鏡像反轉(zhuǎn)4.

對于一棵二叉排序樹，令f=(最大值+最小值)/2，設(shè)計(jì)一個算法，找出距離f值最近、大于f值的結(jié)點(diǎn)。例如，下圖所給定的二叉排序樹中，最大值為7，最小值為1，因此，f=(1+7)/2=4，那么在這棵二叉樹中，距離結(jié)點(diǎn)4最近并且大于4的結(jié)點(diǎn)為5。

（分?jǐn)?shù)：16.50）__________________________________________________________________________________________

正確答案：(首先需要找出二叉排序樹中的最大值與最小值。由于二叉排序樹的特點(diǎn)是：對于任意一個結(jié)點(diǎn)，它的左子樹上所有結(jié)點(diǎn)的值都小于這個結(jié)點(diǎn)的值，它的右子樹上所有結(jié)點(diǎn)的值都大于這個結(jié)點(diǎn)的值。因此，在二叉排序樹中，最小值一定是最左下的結(jié)點(diǎn)，最大值一定是最右下的結(jié)點(diǎn)。根據(jù)最大值與最小值很容易就可以求出f的值。接下來對二叉樹進(jìn)行中序遍歷。如果當(dāng)前結(jié)點(diǎn)的值小于f，那么在這個結(jié)點(diǎn)的右子樹中接著遍歷，否則遍歷這個結(jié)點(diǎn)的左子樹。實(shí)現(xiàn)代碼如下：

classBiTNode:

def__init__(self):

self.data=None

self.lchild=None

self.rchild=None

"""

方法功能:查找值最小的結(jié)點(diǎn)

輸入?yún)?shù):root:根結(jié)點(diǎn)

返回值:值最小的結(jié)點(diǎn)

"""

defgetMinNode(root):

ifroot==None:

returnroot

whileroot.lchild!=None:

root=root.lchild

returnroot

"""

方法功能:查找值最大的結(jié)點(diǎn)

輸入?yún)?shù):root:根結(jié)點(diǎn)

返回值:值最大的結(jié)點(diǎn)

"""

defgetMaxNode(root):

ifroot==None:

returnroot

whileroot.rchild!=None:

root=root.rchild

returnroot

defgetNode(root):

maxNode=getMaxNode(root)

minNode=getMinNode(root)

mid=(maxNode.data+minNode.data)/2

result=None

whileroot!=None:

#當(dāng)前結(jié)點(diǎn)的值不大于f,則在右子樹上找

ifroot.data＜=mid:

root=root.rchild

#否則在左子樹上找

else:

result=root

root=root.lchild

returnresult

if__name__=="__main__":

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

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

printgetNode(root).data

程序的運(yùn)行結(jié)果為：

5

算法性能分析：

這種方法在查找最大結(jié)點(diǎn)與最小結(jié)點(diǎn)時的時間復(fù)雜度為O(h)，h為二叉樹的高度，對于有N個結(jié)點(diǎn)的二叉排序樹，最大的高度為O(N)，最小的高度為O(log2N)。同理，在查找滿足條件的結(jié)點(diǎn)的時候，時間復(fù)雜度也是O(h)。綜上所述，這種方法的時間復(fù)雜度在最好的情況下是O(logN)，最壞的情況下為O(N)。)解析：[考點(diǎn)]如何在二叉排序樹中找出第一個大于中間值的結(jié)點(diǎn)5.

給定一棵二叉樹，求各個路徑的最大和，路徑可以以任意結(jié)點(diǎn)作為起點(diǎn)和終點(diǎn)。比如給定以下二叉樹：

最大和的路徑為結(jié)點(diǎn)5→2→3，這條路徑的和為10，因此返回10。

（分?jǐn)?shù)：16.50）__________________________________________________________________________________________

正確答案：(本題可以通過對二叉樹進(jìn)行后序遍歷來解決，具體思路如下：

對于當(dāng)前遍歷到的結(jié)點(diǎn)root，假設(shè)已經(jīng)求出在遍歷root結(jié)點(diǎn)前最大的路徑和為max：

(1)求出以root.left為起始結(jié)點(diǎn)，葉子結(jié)點(diǎn)為終結(jié)點(diǎn)的最大路徑和為maxLeft；

(2)同理求出以root.right為起始結(jié)點(diǎn)，葉子結(jié)點(diǎn)為終結(jié)點(diǎn)的最大路徑和maxRight。

包含root結(jié)點(diǎn)的最長路徑可能包含如下三種情況：

(1)leftMax=root.val+maxLeft(左子樹最大路徑和可能為負(fù))。

(2)rightMax=root.val+maxRight(右子樹最大路徑和可能為負(fù))。

(3)allMax=root.val+maxLeft+maxRight(左右子樹的最大路徑和都不為負(fù))。

因此，包含root結(jié)點(diǎn)的最大路徑和為tmpMax=max(leftMax,rightMax,allMax)。

在求出包含root結(jié)點(diǎn)的最大路徑后，如果tmpMax＞max，那么更新最大路徑和為tmpMax。

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

classTreeNode:

def__init__(self,val):

self.val=val

self.left=None

self.right=None

classIntRef:

def__init__(self):

self.val=None

#求a,b,c的最大值

defMax(a,b,c):

maxs=aifa＞belseb

maxs=maxsifmaxs＞celseC

returnmaxs

#尋找最長路徑

deffindMaxPathRecursive(root,maxs):

ifNone==root:

return0

else:

#求左子樹以root.left為起始結(jié)點(diǎn)的最大路徑和

sumLeft=findMaxPathRecursive(root.left,maxs)

#求右子樹以root.right為起始結(jié)點(diǎn)的最大路徑和

sumRight=findMaxPathRecursive(root.right,maxs)

#求以root為起始結(jié)點(diǎn),葉子結(jié)點(diǎn)為結(jié)束結(jié)點(diǎn)的最大路徑和

allMax=root.val+sumLeft+sumRight

leftMax=root.val+sumLeft

rightMax=root.val+sumRight

tmpMax=Max(allMax,leftMax,rightMax)

iftmpMax＞maxs.val:

maxs.val=tmpMax

subMax=sumLeftifsumLeft＞sumRightelsesumRight

#返回以root為起始結(jié)點(diǎn),葉子結(jié)點(diǎn)為結(jié)束結(jié)點(diǎn)的最大路徑和

returnroot.val+subMax

deffindMaxPath(root):

maxs=IntRef()

maxs.val=-2**31

findMaxPathRecursive(root,maxs)

returnmaxs.val

if__name__=="__main__":

root=TreeNode(2)

left=TreeNode(3)

right=TreeNode(5)

root.left=left

root.right=right

printfindMaxPath(root)

程序的運(yùn)行結(jié)果為

10

算法性能分析：

二叉樹后序遍歷的時間復(fù)雜度為O(N)，因此，這種方法的時間復(fù)雜度也為O(N)。)解析：[考點(diǎn)]如何在二叉樹中找出路徑最大的和6.

反向DNS查找指的是使用InternetIP地址查找域名。例如，如果你在瀏覽器中輸入06，它會自動重定向到。

如何實(shí)現(xiàn)反向DNS查找緩存?

（分?jǐn)?shù)：17.50）__________________________________________________________________________________________

正確答案：(要想實(shí)現(xiàn)反向DNS查找緩存，主要需要完成如下功能：

(1)將IP地址添加到緩存中的URL映射。

(2)根據(jù)給定IP地址查找對應(yīng)的URL。

對于本題，常見的一種解決方案是使用字典法(使用字典來存儲IP地址與URL之間的映射關(guān)系)，由于這種方法相對比較簡單，這里就不做詳細(xì)的介紹了。下面重點(diǎn)介紹另外一種方法：Trie樹。這種方法的主要優(yōu)點(diǎn)如下：

(1)使用Trie樹，在最壞的情況下的時間復(fù)雜度為O(1)，而哈希方法在平均情況下的時間復(fù)雜度為O(1)；

(2)Trie樹可以實(shí)現(xiàn)前綴搜索(對于有相同前綴的IP地址，可以尋找所有的URL)。

當(dāng)然，由于樹這種數(shù)據(jù)結(jié)構(gòu)本身的特性，所以使用樹結(jié)構(gòu)的一個最大的缺點(diǎn)就是需要耗費(fèi)更多的內(nèi)存，但是對于本題而言，這卻不是一個問題，因?yàn)镮nternetIP地址只包含有11個字母(0到9和.)。所以，本題實(shí)現(xiàn)的主要思路為：在Trie樹中存儲IP地址，而在最后一個結(jié)點(diǎn)中存儲對應(yīng)的域名。實(shí)現(xiàn)代碼如下：

#Trie樹的結(jié)點(diǎn)

classTrieNode:

def__init__(self):

CHAR_COUNT=11

self.isLeaf=False

self.url=None

self.child=[None]*CHAR_COUNT#TrieNode[CHAR_COUNT]#CHAR_COUNT

i=0

whilei＜CHAR_COUNT:

self.child[i]=None

i+=1

defgetIndexFromChar(c):

return10ifc=='.'else(ord(c)-ord('0'))

defgetCharFromIndex(i):

return'.'ifi==10else('0'+str(i))

classDNSCache:

def__init__(self):

self.CHAR_COUNT=11#IP地址最多有11個不同的字符

self.root=TrieNode()#IP地址最大的長度

definsert(self,ip,url):

#IP地址的長度

lens=len(ip)

pCrawl=self.root

level=0

whilelevel＜lens:

#根據(jù)當(dāng)前遍歷到的IP中的字符,找出子結(jié)點(diǎn)的索引

index=getIndexFromChar(ip[level])

#如