LeetCode演算法題-Subtree of Another Tree（Java實現）
這是悅樂書的第265 次更新，第278 篇原創
01 看題和準備
今天介紹的是LeetCode演算法題中Easy級別的第132題（順位題號是572）。給定兩個非空的二進位制樹s和t，檢查樹t是否具有完全相同的結構和具有子樹s的節點值。 s的子樹是一個樹，由s中的節點和所有節點的後代組成。 樹也可以被視為自己的子樹。例如：
鑑於樹s：
3 / \ 45 / \ 12
鑑於樹t：
4 / \ 12
返回true，因為t具有相同的結構和節點值，其子樹為s。
鑑於樹s：
3 / \ 45 / \ 12 / 0
鑑於樹t：
4 / \ 12
返回false。
本次解題使用的開發工具是eclipse，jdk使用的版本是1.8，環境是win7 64位系統，使用Java語言編寫和測試。
02 第一種解法
要判斷t是不是s的子樹，最直接的就是遍歷s的節點，以每一個s的節點為新的子樹去和t比較，而比較的方法需要藉助一個遞迴的方法來完成，來判斷兩個二叉樹是不是相同的結構和相同的值。所以我們需要先使用一個佇列，來遍歷s的每一個節點，拿到每一個節點後，作為新的二叉樹去和t比較，直到找到合適節點開始的子樹與t相同，否則返回false。
public boolean isSubtree(TreeNode s, TreeNode t) {
Queue<TreeNode> queue = new LinkedList<TreeNode>();
queue.offer(s);
while (!queue.isEmpty()) {
TreeNode node = queue.poll();
if (node.left != null) {
queue.offer(node.left);
}
if (node.right != null) {
queue.offer(node.right);
}
if (isSame(node, t)) {
return true;
}
}
return false;
}
public boolean isSame(TreeNode s, TreeNode t){
if (s == null||t == null) {
return s == t;
}
return s.val == t.val && isSame(s.left, t.left) && isSame(s.right, t.right);
}
03 第二種解法
我們也可以把第一種解法的佇列去掉，也換成遞迴的方法，但是思路還是一樣的，需要拿s的每一個節點去比對。
public boolean isSubtree2(TreeNode s, TreeNode t) {
if (s == null) {
return false;
}
return isSame2(s, t) || isSubtree2(s.left, t) || isSubtree2(s.right, t);
}
public boolean isSame2(TreeNode s, TreeNode t){
if (s == null||t == null) {
return s == t;
}
return s.val == t.val && isSame(s.left, t.left) && isSame(s.right, t.right);
}
04 第三種解法
將上面的解法再精簡下，只使用一個遞迴方法。我們知道，只有在s中找到合適的開始節點值（與t的根節點值相等），才能去判斷以該節點作為開始節點的子樹是否和t是相同結構的，找不到就只能繼續找s的左節點值或右節點值了。
要想只使用一個遞迴，那麼必須再引入一個引數，來判斷當前s的節點值是否與t的根節點值相等。如果相等，那麼依次遍歷s當前節點的左右節點與t的左右子節點，要是所有節點值都相等，那麼就可以返回true。如果不相等，那麼就需要兵分兩路，s當前節點的左節點與t繼續比較，s當前節點的右節點與t繼續比較，並且第三個引數為false。
public boolean isSubtree3(TreeNode s, TreeNode t) {
return isSameTree(s, t, false);
}
public boolean isSameTree (TreeNode s, TreeNode t, boolean flag) {
if (s == null||t == null) {
return s == t;
}
if (flag && s.val != t.val) {
return false;
}
if (s.val == t.val) {
if (isSameTree(s.left, t.left, true) && isSameTree(s.right, t.right, true)) {
return true;
}
}
return isSameTree(s.left, t, false) || isSameTree(s.right, t, false);
}
05 第四種解法
我們也可以藉助字串和其子串的思路，將s和t的每一個節點都遍歷出來，組成一個字串，然後去判斷t所組成的字串是不是s所組成字串的子串。
public boolean isSubtree4(TreeNode s, TreeNode t) {
String tree = getTreeString(s, true);
String tree2 = getTreeString(t, true);
return tree.indexOf(tree2) > -1;
}
public String getTreeString(TreeNode t, boolean left) {
if (t == null) {
return left ? "lnull" : "rnull";
}
return "#"+t.val + " " +getTreeString(t.left, true)+" " +getTreeString(t.right, false);
}
06 小結
演算法專題目前已日更超過四個月 ，演算法題文章132 +篇，公眾號對話方塊回覆【資料結構與演算法 】、【演算法 】、【資料結構 】中的任一關鍵詞，獲取系列文章合集。
以上就是全部內容，如果大家有什麼好的解法思路、建議或者其他問題，可以下方留言交流，點贊、留言、轉發就是對我最大的回報和支援！