[[437107]]

Leetcode : https://leetcode-cn.com/problems/shu-de-zi-jie-gou-lcof

“GitHub : https://github.com/nateshao/leetcode/blob/main/algo-notes/src/main/java/com/nateshao/sword_offer/topic_20_isSubStructure/Solution.java

判斷二叉樹A中是否包含子樹B

“題目描述 ：輸入兩棵二叉樹A和B，判斷B是不是A的子結(jié)構(gòu)。(約定空樹不是任意一個(gè)樹的子結(jié)構(gòu))B是A的子結(jié)構(gòu)， 即 A中有出現(xiàn)和B相同的結(jié)構(gòu)和節(jié)點(diǎn)值。例如：給定的樹 A：

       3 
      / \ 
    4   5 
  / \ 
1   2 

給定的樹 B：

4 
 
/ 
 
1 

返回 true，因?yàn)?B 與 A 的一個(gè)子樹擁有相同的結(jié)構(gòu)和節(jié)點(diǎn)值。示例 1：

輸入：A = [1,2,3], B = [3,1] 
 
輸出：false 

示例 2：

輸入：A = [3,4,5,1,2], B = [4,1] 
 
輸出：true 

限制：0 <= 節(jié)點(diǎn)個(gè)數(shù) <= 10000

解題思路:若樹B是樹A的子結(jié)構(gòu),則子結(jié)構(gòu)的根節(jié)點(diǎn)可能為樹A的任意一個(gè)節(jié)點(diǎn)。因此,判斷樹B是否是樹A的子結(jié)構(gòu)，需完成以下兩步工作:

先序遍歷樹A中的每個(gè)節(jié)點(diǎn)nA ; (對(duì)應(yīng)函數(shù) isSubStructure(A, B) )

判斷樹A中以nA為根節(jié)點(diǎn)的子樹否包含樹B。(對(duì)應(yīng)函數(shù)recur(A,B))

算法流程：

“名詞規(guī)定：樹 A 的根節(jié)點(diǎn)記作 節(jié)點(diǎn) A ，樹 B 的根節(jié)點(diǎn)稱為 節(jié)點(diǎn) B 。

recur(A, B) 函數(shù)：

1.終止條件：

• 當(dāng)節(jié)點(diǎn) B為空：說明樹 B 已匹配完成(越過葉子節(jié)點(diǎn))，因此返回 true ;
• 當(dāng)節(jié)點(diǎn) A為空：說明已經(jīng)越過樹 A 葉子節(jié)點(diǎn)，即匹配失敗，返回 false ;
• 當(dāng)節(jié)點(diǎn) A 和 B 的值不同：說明匹配失敗，返回 false ;

2.返回值：

• 判斷A和B的左子節(jié)點(diǎn)是否相等，即recur(A. left, B. left) ;
• 判斷A和B的右子節(jié)點(diǎn)是否相等,即recur(A. right，B. right) ;

isSubStructure(A, B)函數(shù):

• 特例處理 ：當(dāng)樹A為空或樹B為空時(shí)，直接返回false;
• 返回值 ：若樹B是樹A的子結(jié)構(gòu),則必滿足以下三種情況之一,因此用或|連接;
  • 以節(jié)點(diǎn)A為根節(jié)點(diǎn)的子樹包含樹B，對(duì)應(yīng)recur(A,B);
  • 樹B是樹A左子樹的子結(jié)構(gòu),對(duì)應(yīng)isSubStructure(A. left， B) ;
  • 樹B是樹A右子樹的子結(jié)構(gòu)，對(duì)應(yīng)isSubStructure(A. right, B) ;

以讓 2. 3.實(shí)質(zhì)上是在對(duì)樹A做先序遍歷。

復(fù)雜度分析:

• 時(shí)間復(fù)雜度O(MN)： 中M,N分別為樹A和樹B的節(jié)點(diǎn)數(shù)量;先序遍歷樹A占用0(M),每次調(diào)用recur(A, B)判斷占用O(N)。
• 空間復(fù)雜度O(M)：
  • 當(dāng)樹A和樹B都退化為鏈表時(shí)，遞歸調(diào)用深度最大。
  • 當(dāng)M≤N時(shí)，遍歷樹A與遞歸判斷的總遞歸深度為M ;
  • 當(dāng)M> N時(shí)，最差情況為遍歷至樹A葉子節(jié)點(diǎn)，此時(shí)總遞歸深度為M。

package com.nateshao.sword_offer.topic_20_isSubStructure; 
 
/** 
 * @date Created by 邵桐杰 on 2021/11/23 19:19 
 * @微信公眾號(hào) 程序員千羽 
 * @個(gè)人網(wǎng)站 www.nateshao.cn 
 * @博客 https://nateshao.gitee.io 
 * @GitHub https://github.com/nateshao 
 * @Gitee https://gitee.com/nateshao 
 * Description: 判斷二叉樹A中是否包含子樹B 
 */ 
class Solution { 
 
    /** 
     * 精選解答 
     * @param A 
     * @param B 
     * @return 
     */ 
    public static boolean isSubStructure1(TreeNode A, TreeNode B) { 
        return (A != null && B != null) && (recur1(A, B) || isSubStructure1(A.left, B) || isSubStructure1(A.right, B)); 
    } 
 
    public static boolean recur1(TreeNode A, TreeNode B) { 
        if (B == null) return true; 
        if (A == null || A.val != B.val) return false; 
        return recur1(A.left, B.left) && recur1(A.right, B.right); 
    } 
     
    /*********************************** 法二 *********************************************/ 
    //遍歷A的每一個(gè)節(jié)點(diǎn) 
    public boolean isSubStructure(TreeNode A, TreeNode B) { 
        if (A == null || B == null) return false;//約定空樹不是任意一個(gè)樹的子結(jié)構(gòu) 
        return recur(A, B) || isSubStructure(A.left, B) || isSubStructure(A.right, B); 
    } 
 
    //同時(shí)遍歷A和B的相同位置節(jié)點(diǎn) 
    boolean recur(TreeNode A, TreeNode B) { 
        //當(dāng)B某個(gè)節(jié)點(diǎn)為null，則無需比較了，直接返回true，比較其他節(jié)點(diǎn) 
        if (B == null) return true; 
        //如果相同位置的兩個(gè)節(jié)點(diǎn)不相同，則返回false，不用再繼續(xù)比較了 
        if (A == null || A.val != B.val) return false; 
        //繼續(xù)往下遍歷比較 
        return recur(A.left, B.left) && recur(A.right, B.right); 
    } 
 
    public class TreeNode { 
        int val; 
        TreeNode left; 
        TreeNode right; 
 
        TreeNode(int x) { 
            val = x; 
        } 
    } 
} 

參考鏈接：https://leetcode-cn.com/problems/shu-de-zi-jie-gou-lcof/solution/mian-shi-ti-26-shu-de-zi-jie-gou-xian-xu-bian-li-p