572. 另一個樹的子樹
題目來源：https://leetcode-cn.com/problems/subtree-of-another-tree
題目
給定兩個非空二叉樹 s 和 t，檢驗 s 中是否包含和 t 具有相同結構和節點值的子樹，s 的一個子樹包括 s 的一個節點和這個節點的所有子孫，s 也可以看做它自身的一棵子樹，
示例 1:
給定的樹 s:
3
/ \
4 5
/ \
1 2
給定的樹 t：
4
/ \
1 2
回傳 true，因為 t 與 s 的一個子樹擁有相同的結構和節點值，
示例 2:
給定的樹 s：
3
/ \
4 5
/ \
1 2
/
0
給定的樹 t：
4
/ \
1 2
回傳 false，
解題思路
思路：深度優先搜索
在這里，先分析題意：
- 一個二叉樹若為另一個樹的子樹，則它含有與另外一個樹的子樹相同結構和節點值，
- 根據示例 2 可知，判斷是否為子樹，必須有完全相同結構和節點值，
以下 s、t 表示兩個二叉樹，題目要求判斷 t 是否是 s 的子樹
現在將題意轉換為可實作代碼書寫的思路，判斷兩個樹是否相等，那么下面的條件必須同時成立：
- 當前兩個樹根節點值相同；
- s 的左子樹與 t 的左子樹相同；
- s 的右子樹與 t 的右子樹相同，
根據上面的思路，本篇幅考慮使用深度優化搜索的方法，列舉 s 的每個節點，判斷這個點的子樹是否與 t 相等，使用深度優先搜索檢查，從根出發，同步移動遍歷兩個樹，判斷相應的位置是否相等，
具體的代碼實作如下，
代碼實作
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def isSubtree(self, s: TreeNode, t: TreeNode) -> bool:
return self.dfs(s, t)
def dfs(self, c, t):
# c 子樹為空時，回傳 False
if not c:
return False
return self.is_same(c, t) or self.dfs(c.left, t) or self.dfs(c.right, t)
def is_same(self, c, t):
# 兩個樹都為空時，也認為是相同
if (not c) and (not t):
return True
# 當其中一個樹為空，但另外一個樹不為空時，此時則為不同
if (not c and t) or (c and not t):
return False
# 兩個樹都不為空，若值不同，也為不同
if (c.val != t.val):
return False
# 上面的情況都不符合時，繼續向下檢查
return self.is_same(c.left, t.left) and self.is_same(c.right, t.right)
實作結果
以上就是使用深度優先搜索，列舉 s 的每個節點與 t 進行匹配，進而解決《572. 另一個樹的子樹》問題的主要內容，
歡迎關注微信公眾號《書所集錄》
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/149339.html
標籤：Python
上一篇：python 基礎知識5-集合
下一篇：Python if陳述句