JZ26 樹的子結構
描述
輸入兩棵二叉樹A，B，判斷B是不是A的子結構，（我們約定空樹不是任意一個樹的子結構）
假如給定A為{8,8,7,9,2,#,#,#,#,4,7}，B為{8,9,2}，2個樹的結構如下，可以看出B是A的子結構
題解1 深度遍歷
思路
既然是要找到A樹中是否有B樹這樣子樹，如果是有子樹肯定是要遍歷這個子樹和B樹，將兩個的節點一一比較，但是這樣的子樹不一定就是A樹根節點開始的，所以我們還要先找到子樹可能出現的位置，
既然是可能的位置，那我們可以對A樹的每個節點前序遞回遍歷，尋找是否有這樣的子樹，而尋找是否有子樹的時候，我們就將A樹與B樹同步前序遍歷，依次比較節點值，
具體做法：
step 1：因為空樹不是任何樹的子樹，所以要先判斷B樹是否為空樹，
step 2：當A樹為空節點，但是B樹還有節點的時候，不為子樹，但是A樹不為空節點，B樹為空節點時可以是子樹，
step 3：每次遞回比較A樹從當前節點開始，是否與B樹完全一致，同步前序遍歷，
step 4：A樹自己再前序遍歷進入子節點，當作子樹起點再與B樹同步遍歷，
step 5：以上情況任意只要有一種即可，
代碼
public class Solution {
public boolean HasSubtree(TreeNode root1, TreeNode root2) {
if (root2 == null) return false;
//一個節點為空 一節點不為空
if (root1 == null) return false;
boolean flag1 = recursion(root1, root2);
boolean flag2 = HasSubtree(root1.left, root2);
boolean flag3 = HasSubtree(root1.right, root2);
return flag1 || flag2 || flag3;
}
// 判斷是否有相等的根節點
public boolean recursion(TreeNode root1, TreeNode root2) {
//一個節點為空 一節點不為空
if (root1 == null && root2 != null) return false;
if (root1 == null || root2 == null) return true;
if (root1.val != root2.val) return false;
return recursion(root1.left, root2.left) && recursion(root1.right, root2.right);
}
}
題解2 廣度遍歷
思路
首先對于A樹層次遍歷每一個節點，遇到一個與B樹根節點相同的節點，我們就開始同步層次遍歷比較以這個節點為根的樹中是否出現了B樹的全部節點，因為我們只考慮B樹的所有節點是否在A樹中全部出現，那我們就以B樹為基，再進行一次層次遍歷，A樹從那個節點開始跟隨B樹一致進行層次遍歷就行了，比較對應的每個點是否相同，或者B樹是否有超出A樹沒有的節點，
具體做法：
step 1：先判斷空樹，空樹不為子結構，
step 2：利用佇列輔助，層次遍歷第一棵樹，每次檢查遍歷到的節點是否和第二棵樹的根節點相同，
step 3：若是相同，可以以該節點為子樹根節點，再次借助佇列輔助，同步層次遍歷這個子樹與第二棵樹，這個時候以第二棵樹為基，只要找到第二棵樹的全部節點，就算找到了子結構，
代碼
package mid.JZ26樹的子結構;
import java.util.LinkedList;
class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
public class Solution {
public boolean HasSubtree(TreeNode root1, TreeNode root2) {
if (root2 == null) return false;
//一個節點為空 一節點不為空
if (root1 == null) return false;
LinkedList<TreeNode> q = new LinkedList<>();
q.offer(root1);
while (!q.isEmpty()) {
TreeNode node = q.poll();
if (node.val == root2.val) {
if (helper(node, root2)) {
return true;
}
}
if (node.left != null) q.offer(node.left);
if (node.right != null) q.offer(node.right);
}
return false;
}
public boolean helper(TreeNode root1, TreeNode root2) {
LinkedList<TreeNode> q1 = new LinkedList<>();
LinkedList<TreeNode> q2 = new LinkedList<>();
q1.offer(root1);
q2.offer(root2);
while (!q2.isEmpty()) {
TreeNode node1 = q1.poll();
TreeNode node2 = q2.poll();
//樹1為慷訓者二者不相等
if (node1 == null || node1.val != node2.val)
return false;
//樹2還有左子樹
if (node2.left != null) {
//子樹入隊
q1.offer(node1.left);
q2.offer(node2.left);
}
//樹2還有右子樹
if (node2.right != null) {
//子樹入隊
q1.offer(node1.right);
q2.offer(node2.right);
}
}
return true;
}
}
// 深度遍歷查詢
/*public class Solution {
public boolean HasSubtree(TreeNode root1, TreeNode root2) {
if (root2 == null) return false;
//一個節點為空 一節點不為空
if (root1 == null) return false;
boolean flag1 = recursion(root1, root2);
boolean flag2 = HasSubtree(root1.left, root2);
boolean flag3 = HasSubtree(root1.right, root2);
return flag1 || flag2 || flag3;
}
// 判斷是否有相等的根節點
public boolean recursion(TreeNode root1, TreeNode root2) {
//一個節點為空 一節點不為空
if (root1 == null && root2 != null) return false;
if (root1 == null || root2 == null) return true;
if (root1.val != root2.val) return false;
return recursion(root1.left, root2.left) && recursion(root1.right, root2.right);
}
}*/
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/539099.html
標籤：其他