輸入兩棵二叉樹 A，B，判斷 B 是不是 A 的子結構，我們約定空樹不是任意一個樹的子結構
基本思路：
-
首先在 A 中找到與 B 的根結點的值一樣的結點，可以使用遞回遍歷查找
-
找到的話，判斷 A 中該結點對應的子樹是否與 B 相等，相等回傳 true，方法結束，否則回傳 false，方法繼續執行
-
繼續在 A 中遍歷查找與 B 的根結點的值一致的結點，找到的話重復第二步，如果不存在這樣的結點，直接回傳 false
public class Solution {
public boolean HasSubtree(TreeNode root1,TreeNode root2) {
boolean result = false;
// 當 Tree1 和 Tree2 都不為 null 時，才進行比較，否則直接回傳 false
if(root2 != null && root1 != null) {
// 如果找到了對應 Tree2 的根節點的點
if(root1.val == root2.val) {
// 以這個根節點為起點判斷是否包含 Tree2
result = doesTree1HaveTree2(root1, root2);
}
// 如果找不到，那么就再去找 root 的左兒子當起點，判斷是否包含 Tree2
if(!result) {
result = HasSubtree(root1.left, root2);
}
// 如果還找不到，那么就再去找 root 的右兒子當起點，去判斷是否包含 Tree2
if(!result) {
result = HasSubtree(root1.right, root2);
}
}
// 回傳結果
return result;
}
public boolean doesTree1HaveTree2(TreeNode node1,TreeNode node2) {
// 如果 Tree2 已經遍歷完了都能對應的上，回傳 true
// 注意這里必須先判斷 node2，因為 Tree1 和 Tree2 是同步比較的，此時 node1 可能為 null，也可能不為 null
if(node2 == null) {
return true;
}
//如果 Tree2 還沒有遍歷完，Tree1 卻遍歷完了,回傳false
if(node1 == null) {
return false;
}
//如果其中有一個點沒有對應上，回傳 false
if (node1.val != node2.val) {
return false;
}
// 如果根節點對應的上，那么就分別去子節點里面匹配
return doesTree1HaveTree2(node1.left,node2.left) && doesTree1HaveTree2(node1.right,node2.right);
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/138416.html
標籤：其他