溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
這篇文章主要為大家展示了“LeetCode中怎么判斷樹的子結構”，內容簡而易懂，條理清晰，希望能夠幫助大家解決疑惑，下面讓小編帶領大家一起研究并學習一下“LeetCode中怎么判斷樹的子結構”這篇文章吧。
問題描述
輸入兩棵二叉樹A和B，判斷B是不是A的子結構。(約定空樹不是任意一個樹的子結構)
B是A的子結構， 即A中有出現和B相同的結構和節點值。
例如:
給定的樹 A:
3
/ \
4 5
/ \
1 2
給定的樹 B：
4
/
1
返回 true，因為 B 與 A 的一個子樹擁有相同的結構和節點值。
示例 1：
輸入：A = [1,2,3], B = [3,1]
輸出：false
示例 2：
輸入：A = [3,4,5,1,2], B = [4,1]
輸出：true
限制：
0 <= 節點個數 <= 10000
問題分析
要判斷B是否是A的子結構，像下面這樣，我們只需要從根節點開始判斷，通過遞歸的方式比較他的每一個子節點即可，所以代碼也很容易寫
1public boolean isSubStructure(TreeNode A, TreeNode B) {
2 //邊界條件判斷，如果A和B有一個為空，返回false
3 if (A == null || B == null)
4 return false;
5 return isSub(A, B);
6}
7
8boolean isSub(TreeNode A, TreeNode B) {
9 //這里如果B為空，說明B已經訪問完了，確定是A的子結構
10 if (B == null)
11 return true;
12 //如果B不為空A為空，或者這兩個節點值不同，說明B樹不是
13 //A的子結構，直接返回false
14 if (A == null || A.val != B.val)
15 return false;
16 //當前節點比較完之后還要繼續判斷左右子節點
17 return isSub(A.left, B.left) && isSub(A.right, B.right);
18}
但實際上B如果是A的子結構的話，不一定是從根節點開始的，也可能是下面這樣
也就是說B不光有可能是A的子結構，也有可能是A左子樹的子結構或者右子樹的子結構，所以如果從根節點判斷B不是A的子結構，還要繼續判斷B是不是A左子樹的子結構和右子樹的子結構，代碼如下
1public boolean isSubStructure(TreeNode A, TreeNode B) {
2 if (A == null || B == null)
3 return false;
4 //先從根節點判斷B是不是A的子結構，如果不是在分別從左右兩個子樹判斷，
5 //只要有一個為true，就說明B是A的子結構
6 return isSub(A, B) || isSubStructure(A.left, B) || isSubStructure(A.right, B);
7}
8
9boolean isSub(TreeNode A, TreeNode B) {
10 //這里如果B為空，說明B已經訪問完了，確定是A的子結構
11 if (B == null)
12 return true;
13 //如果B不為空A為空，或者這兩個節點值不同，說明B樹不是
14 //A的子結構，直接返回false
15 if (A == null || A.val != B.val)
16 return false;
17 //當前節點比較完之后還要繼續判斷左右子節點
18 return isSub(A.left, B.left) && isSub(A.right, B.right);
19}以上是“LeetCode中怎么判斷樹的子結構”這篇文章的所有內容，感謝各位的閱讀！相信大家都有了一定的了解，希望分享的內容對大家有所幫助，如果還想學習更多知識，歡迎關注億速云行業資訊頻道！
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
