子結構判斷

LCR 143. 子結構判斷

參考題解

題前知識

1）子結構

首先我們先了解一下子結構：

• 原題信息：判斷 tree2 是否以 tree1 的某個節點為根的子樹具有 相同的結構和節點值 。
• 子結構也就是B樹是否含于A樹左子樹或者右子樹之中，并且具有相同的結構和節點值，或者是否以A樹的根節點作為子樹

2）先序遍歷

該題使用到了先序遍歷，先序遍歷相關代碼

先序遍歷規則：根左右

public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        dfs(res, root);
        return res;
}
private void dfs(List<Integer> res, TreeNode root){
    if(root == null){
        return;
    }
    res.add(root.val);
    dfs(res, root.left);
    dfs(res, root.right);

}

正題

我們可以使用先序遍歷樹A的每個節點，然后我們判斷A樹是否包含B樹

由于我們判斷A樹是否包含B樹是從根節點開始匹配的，所以先序遍歷的更合適本題

判斷A樹是否包含B樹

終止條件

• B為空，說明B已經匹配完成，返回true;
• A為空，匹配失敗，B樹已經越過了A的葉子結點，超出范圍了，返回false;
• A的節點值和B的節點值不一樣，返回false

返回條件

• 判斷A的左節點是否和B的左節點相等 –> recur(A.left, B.left)
• 判斷A的右節點是否和B的右節點相等 –> recur(A.right, B.right)

public boolean recur(TreeNode A, TreeNode B) {
    if(B == null) return true;
    if(A == null || A.val != B.val) return false;
    return recur(A.left, B.left) && recur(A.right, B.right);
}

isSubStructure(A, B)函數

邊界條件

• A樹或者B樹為null，返回false

三種情況

• 以A的根節點為子樹包含B
• 以A的左子樹為子樹包含B
• 以A的右子樹為子樹包含B

以上情況只要符合一種就返回true

最終代碼：

通過recur(A, B)找到B的根節點和B的子節點是否和A的匹配

public boolean isSubStructure(TreeNode A, TreeNode B) {
        return (A != null && B != null) && (recur(A, B) || isSubStructure(A.left, B) || isSubStructure(A.right, B));
}

public boolean recur(TreeNode A, TreeNode B) {
    if(B == null) return true;
    if(A == null || A.val != B.val) return false;
    return recur(A.left, B.left) && recur(A.right, B.right);
}

題后解析

關于題中用到的先序遍歷思想

1、isSubStructure(A, B)中的先序遍歷

對于樹A的某個節點：

1. 先訪問根節點：執行 recur(A, B) 檢查當前節點是否能作為匹配的起點
2. 再遍歷左子樹：如果根節點不匹配，遞歸調用 isSubStructure(A.left, B)
3. 最后遍歷右子樹：如果左子樹也沒有找到，遞歸調用 isSubStructure(A.right, B)

2、recur 方法中的先序遍歷

• 先比較當前根節點的值 (A.val != B.val)
• 再遞歸比較左子樹 (recur(A.left, B.left))
• 最后遞歸比較右子樹 (recur(A.right, B.right))