本系列針對面試中【經典】資料結構類算法題進行分類和彙總，每篇講解一種資料結構的高頻面試題。本篇的主角是樹。
本文結構：
1. 面試前必須知道的[樹]的基礎知識。
2. [樹]的經典手寫程式設計題。
基礎知識
基礎概念
基礎性質
經典面試題
- 二叉樹以及二叉搜尋樹初始化
class Node():
def __init__(self, x):
self.val = x
self.left = None
self.right = None
class Tree():
def __init__(self):
self.root = None
def rand_tree(self, x): #普通二叉樹建構
node = Node(x)
if not self.root:
self.root = node
return
temp = [self.root]
while True:
p = temp.pop(0)
if not p.left:
p.left = node
return
elif not p.right:
p.right = node
return
temp.append(p.left)
temp.append(p.right)
def sort_tree(self, x): #搜尋二叉樹建構
node = Node(x)
if not self.root:
self.root = node
return
p = self.root
while True:
if x<p.val:
if not p.left:
p.left = node
return
p = p.left
elif x>=p.val:
if not p.right:
p.right = node
return
p = p.right 複制
- 層次周遊
def traverse(root):
if not root:
return
temp = [root]
res = []
while temp:
p = temp.pop(0)
res.append(p.val)
if p.left:
temp.append(p.left)
if p.right:
temp.append(p.right)
return res 複制
- 前序周遊
#遞歸版
def preoder_recursion(root):
if not root:
return []
left = preoder_recursion(root.left)
res = [root.val]
right = preoder_recursion(root.right)
return res+left+right
#非遞歸版
def preorder(root):
if not root:
return
res = []
temp = [root]
while temp:
while temp[-1]:
res.append(temp[-1].val)
temp.append(temp[-1].left)
temp.pop()
if temp:
p = temp.pop()
temp.append(p.right)
return res 複制
- 中序周遊
#遞歸版
def inorder_recursion(root):
if not root:
return []
left = inorder_recursion(root.left)
res = [root.val]
right = inorder_recursion(root.right)
return left+res+right
#非遞歸
def inorder(root):
if not root:
return
res = []
temp = [root]
while temp:
while temp[-1]:
temp.append(temp[-1].left)
temp.pop()
if temp:
p = temp.pop()
res.append(p.val)
temp.append(p.right)
return res 複制
- 後續周遊
#遞歸版
def postorder_recursion(root):
if not root:
return []
left = postorder_recursion(root.left)
res = [root.val]
right = postorder_recursion(root.right)
return left+right+res
#非遞歸版
def postorder(root):
if not root:
return
res = []
temp = [root]
while temp:
while temp[-1]:
p = temp[-1]
if p.right:
temp.append(None) #用None作為分隔
temp.append(p.right)
else:
temp.append(p.right)
temp.append(p.left)
temp.pop()
if temp:
if not temp[-1]:
temp.pop()
res.append(temp.pop().val)
else:
res.append(temp.pop().val)
return res 複制
- 重建二叉樹
pre = [3,0,1,2,6,5,4,8,7,9]
mid = [0,1,2,3,4,5,6,7,8,9]
pos = [2,1,0,4,5,7,9,8,6,3]
要求不含重複數字，對于根據後序和前序周遊重建二叉樹要求二叉樹是搜尋二叉樹，不然結構不确定。
#根據前序和中序周遊
def reconstruct_1(pre, mid):
if len(pre)==0:
return None
elif len(pre)==1:
return Node(pre[0])
root = mid.index(pre[0])
flag = Node(pre[0])
flag.left = reconstruct_1(pre[1:root+1], mid[:root])
flag.right = reconstruct_1(pre[root+1:], mid[root+1:])
return flag
#根據後序和中序周遊
def reconstruct_2(pos, mid):
if len(pos)==0:
return None
elif len(pos)==1:
return Node(pos[0])
root = mid.index(pos[-1])
flag = Node(pos[-1])
flag.left = reconstruct_2(pos[:root], mid[:root])
flag.right = reconstruct_2(pos[root:-1], mid[root+1:])
return flag
#根據前序和後序周遊
def reconstruct_3(pre, pos):
print(pre)
print(pos)
if len(pos)==0:
return None
elif len(pos)==1:
return Node(pos[0])
index = pos.index(pre[1])
flag = Node(pre[0])
if index==len(pos)-2:
if flag.val<pos[0]: #判斷應該在左子樹還是右子樹，是以要求是二叉搜尋樹
flag.right = reconstruct_3(pre[1:], pos[:-1])
else:
flag.left = reconstruct_3(pre[1:], pos[:-1])
else:
flag.left = reconstruct_3(pre[1:index+2], pos[:index+1])
flag.right = reconstruct_3(pre[index+2:], pos[index+1:-1])
return flag 複制
- 樹的子結構
輸入兩棵二叉樹A，B，判斷B是不是A的子結構。（我們約定空樹不是任意一個樹的子結構）。
class Solution:
def HasSubtree(self, pRoot1, pRoot2):
# write code here
if not pRoot1 or not pRoot2:
return False
return self.is_subtree(pRoot1, pRoot2) or self.HasSubtree(pRoot1.left, pRoot2) or self.HasSubtree(pRoot1.right, pRoot2)
def is_subtree(self, a, b):
if not b:
return True
if not a or a.val != b.val:
return False
return self.is_subtree(a.left, b.left) and self.is_subtree(a.right, b.right) 複制
- 二叉樹的鏡像
将給定的二叉樹變換為其鏡像。
class Solution():
def Mirror(self, root):
if not root:
return
if not root.left and not root.right:
return
root.left, root.right = root.right, root.left
self.Mirror(root.left)
self.Mirror(root.right)
return root 複制
- 二叉樹中和為某一值的路徑
輸入一顆二叉樹的跟節點和一個整數，列印出二叉樹中結點值的和為輸入整數的所有路徑。路徑定義為從樹的根結點開始往下一直到葉結點所經過的結點形成一條路徑。(注意: 在傳回值的list中，數組長度大的數組靠前)
class Solution():
def FindPath(self, root, expectNumber):
if not root:
return []
if not root.left and not root.right and root.val==expectNumber:
return [[root.val]]
res = []
left = self.FindPath(root.left, expectNumber-root.val)
right = self.FindPath(root.right, expectNumber-root.val)
for i in left+right:
res.append([root.val]+i)
return res 複制
- 二叉搜尋樹與雙向連結清單
輸入一棵二叉搜尋樹，将該二叉搜尋樹轉換成一個排序的雙向連結清單。要求不能建立任何新的結點，隻能調整樹中結點指針的指向。
class Solution:
def __init__(self):
self.listHead = None
self.listTail = None
def Convert(self, pRootOfTree):
if not pRootOfTree:
return
self.Convert(pRootOfTree.left)
if not self.listHead:
self.listHead = pRootOfTree
self.listTail = pRootOfTree
else:
self.listTail.right = pRootOfTree
pRootOfTree.left = self.listTail
self.listTail = pRootOfTree
self.Convert(pRootOfTree.right)
return self.listHead 複制
- 二叉樹的深度
#遞歸版
class Solution():
def TreeDepth(self, pRoot):
if not pRoot:
return 0
left = self.TreeDepth(pRoot.left)
right = self.TreeDepth(pRoot.right)
return left+1 if left>right else right+1
#循環版
def TreeDepth(self, pRoot):
if not pRoot:
return 0
p = [pRoot]
last = p[-1]
layer = 0
while p:
p1 = p.pop(0)
if p1.left:
p.append(p1.left)
if p1.right:
p.append(p1.right)
if p1==last:
layer += 1
if p:
last = p[-1]
return layer 複制
- 平衡二叉樹
輸入一棵二叉樹的根節點，判斷該樹是不是平衡二叉樹。如果某二叉樹中任意節點的左、右子樹的深度相差不超過1，那麼它就是平衡二叉樹。
class Solution:
def IsBalanced_Solution(self, pRoot):
if not pRoot:
return True
if abs(self.TreeDepth(pRoot.left)-self.TreeDepth(pRoot.right))>1:
return False
return self.IsBalanced_Solution(pRoot.left) and self.IsBalanced_Solution(pRoot.right)
def TreeDepth(self, pRoot):
if not pRoot:
return 0
left = self.TreeDepth(pRoot.left)
right = self.TreeDepth(pRoot.right)
return max(left+1, right+1) 複制
- 二叉樹的下一個結點
給定一個二叉樹和其中的一個結點，請找出中序周遊順序的下一個結點并且傳回。注意，樹中的結點不僅包含左右子結點，同時包含指向父結點的指針。
class TreeLinkNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
self.next = None
class Solution:
def GetNext(self, pNode):
if not pNode:
return None
if pNode.right:
p = pNode.right
while p.left:
p = p.left
return p
else:
while pNode.next:
if pNode.next.left==pNode:
return pNode.next
pNode = pNode.next
return None 複制
- 對稱的二叉樹
請實作一個函數，用來判斷一顆二叉樹是不是對稱的。注意，如果一個二叉樹同此二叉樹的鏡像是同樣的，定義其為對稱的。
（1）如果左右子樹有一個為空，那麼該二叉樹肯定不是對稱二叉樹
（2）如果左右子樹均不為空，但是節點的值不同，那麼該二叉樹肯定不是對稱二叉樹
class Solution:
#對稱比較方法，其實也就是前序和鏡像前序周遊比較的方法，和下面的對稱周遊方法一個意思
def isSymmetrical(self, pRoot):
if not pRoot:
return True
if (pRoot.left and not pRoot.right) or (pRoot.right and not pRoot.left):
return False
return self.iSame(pRoot.left, pRoot.right)
def iSame(self, p1, p2):
if not p1 and not p2:
return True
if not p1 or not p2 or (p1.val!=p2.val):
return False
return self.iSame(p1.left, p2.right) and self.iSame(p1.right, p2.left)
#對稱周遊方法（先存儲後比較）
def isSymmetrical(self, pRoot):
if not pRoot:
return True
if (pRoot.left and not pRoot.right) or (pRoot.right and not pRoot.left):
return False
return self.preorder(pRoot) == self.preorder_n(pRoot)
def preorder(self, pRoot):
if not pRoot:
return [None]
left = self.preorder(pRoot.left)
right = self.preorder(pRoot.right)
return [pRoot.val]+left+right
def preorder_n(self, pRoot):
if not pRoot:
return [None]
left = self.preorder_n(pRoot.left)
right = self.preorder_n(pRoot.right)
return [pRoot.val]+right+left 複制
- 按之字形順序列印二叉樹
請實作一個函數按照之字形列印二叉樹，即第一層按照從左到右的順序列印，第二層按照從右至左的順序列印，第三層按照從左到右的順序列印，其他行以此類推。
class Solution:
def Print(self, pRoot):
if not pRoot:
return []
res = []
res_1 = []
temp = [pRoot]
left_to_right = 1
last = temp[-1]
while temp:
p = temp.pop(0)
res_1.append(p.val)
if p.left:
temp.append(p.left)
if p.right:
temp.append(p.right)
if p==last:
res.append(res_1 if left_to_right else res_1[::-1])
left_to_right = not left_to_right
res_1 = []
if temp:
last = temp[-1]
return res 複制
- 序列化二叉樹
請實作兩個函數，分别用來序列化和反序列化二叉樹
class Solution:
def Serialize(self, root):
if not root:
return '#,'
s = str(root.val) + ','
left = self.Serialize(root.left)
right = self.Serialize(root.right)
s += left + right
return s
def Deserialize(self, s):
list1 = s.split(',')
return self.deserializeTree(list1)
def deserializeTree(self, list1):
if len(list1)<=0:
return None
val = list1.pop(0)
root = None # 每次遞歸需要初始化，不然程式不知道是全局變量還是局部變量
if val != '#':
root = Node(int(val))
root.left = self.deserializeTree(list1)
root.right = self.deserializeTree(list1)
return root 複制
- 二叉搜尋樹的第k個結點
class Solution:
def KthNode(self, pRoot, k):
if not pRoot:
return None
temp = [pRoot]
res = []
while temp:
while temp[-1]:
temp.append(temp[-1].left)
temp.pop()
if temp:
p = temp.pop()
res.append(p)
temp.append(p.right)
if len(res)==k:
return res[-1] 複制