題目
難度：★☆☆☆☆
類型：二叉樹
給定兩個非空二叉樹 s 和 t，檢驗 s 中是否包含和 t 具有相同結(jié)構(gòu)和節(jié)點值的子樹。s 的一個子樹包括 s 的一個節(jié)點和這個節(jié)點的所有子孫。s 也可以看做它自身的一棵子樹。
題目
示例 1:
給定的樹 s:
3
/ \
4 5
/ \
1 2
給定的樹 t：
4
/ \
1 2
返回 true，因為 t 與 s 的一個子樹擁有相同的結(jié)構(gòu)和節(jié)點值。
示例 2:
給定的樹 s：
3
/ \
4 5
/ \
1 2
/
0
給定的樹 t：
4
/ \
1 2
返回 false。
解答
這是樹的一個基礎(chǔ)題，判斷一棵樹是否是另一棵的子樹，通過前序遍歷的結(jié)果是否存在包含關(guān)系實現(xiàn)。
class Solution:
def isSubtree(self, s, t):
def pre_order(root, res):
"""
獲得二叉樹的前序遍歷結(jié)果
:param root: 二叉樹根節(jié)點
:param res: 結(jié)果存儲列表
:return:
"""
if root: # 如果當(dāng)前節(jié)點不為空
res.append(str(root.val)) # 添加當(dāng)前結(jié)點的值
pre_order(root.left, res) # 左子樹的前序遍歷
pre_order(root.right, res) # 右子樹的前序遍歷
else: # 如果當(dāng)前結(jié)點為空
res.append('#') # 用“#”代替
s_list, t_list = [], [] # 序列化結(jié)果存儲器
pre_order(s, s_list) # 獲取s的前序遍歷結(jié)果
pre_order(t, t_list) # 獲取t的前序遍歷結(jié)果
# print(','.join(t_list))
# print(','.join(s_list))
# 將列表轉(zhuǎn)為字符串進(jìn)行比較，前端加“，”防止出現(xiàn)“2,#,#”in“12,#,#”中的情況
return ','+','.join(t_list) in ','+','.join(s_list)
同樣，我們可以考慮使用元組精簡上述復(fù)雜的前序遍歷流程：
class Solution:
def isSubtree(self, s, t):
# 這個函數(shù)把樹序列化為一個元組
toTup = lambda n: (n.val, toTup(n.left), toTup(n.right)) if n else None
# 把元組轉(zhuǎn)化為字符串以方便比較
return str(toTup(t)) in str(toTup(s))
如有疑問或建議，歡迎評論區(qū)留言~
