LeetCode中怎么判斷樹(shù)的子結(jié)構(gòu)

輸入兩棵二叉樹(shù)A和B，判斷B是不是A的子結(jié)構(gòu)。(約定空樹(shù)不是任意一個(gè)樹(shù)的子結(jié)構(gòu))

B是A的子結(jié)構(gòu)， 即A中有出現(xiàn)和B相同的結(jié)構(gòu)和節(jié)點(diǎn)值。

例如:

給定的樹(shù) A:

給定的樹(shù) B：

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

示例 1：

示例 2：

限制：

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

要判斷B是否是A的子結(jié)構(gòu)，像下面這樣，我們只需要從根節(jié)點(diǎn)開(kāi)始判斷，通過(guò)遞歸的方式比較他的每一個(gè)子節(jié)點(diǎn)即可，所以代碼也很容易寫

 1public boolean isSubStructure(TreeNode A, TreeNode B) {
2    //邊界條件判斷，如果A和B有一個(gè)為空，返回false
3    if (A == null || B == null)
4        return false;
5    return isSub(A, B);
6}
7
8boolean isSub(TreeNode A, TreeNode B) {
9    //這里如果B為空，說(shuō)明B已經(jīng)訪問(wèn)完了，確定是A的子結(jié)構(gòu)
10    if (B == null)
11        return true;
12    //如果B不為空A為空，或者這兩個(gè)節(jié)點(diǎn)值不同，說(shuō)明B樹(shù)不是
13    //A的子結(jié)構(gòu)，直接返回false
14    if (A == null || A.val != B.val)
15        return false;
16    //當(dāng)前節(jié)點(diǎn)比較完之后還要繼續(xù)判斷左右子節(jié)點(diǎn)
17    return isSub(A.left, B.left) && isSub(A.right, B.right);
18}

但實(shí)際上B如果是A的子結(jié)構(gòu)的話，不一定是從根節(jié)點(diǎn)開(kāi)始的，也可能是下面這樣

 1public boolean isSubStructure(TreeNode A, TreeNode B) {
2    if (A == null || B == null)
3        return false;
4    //先從根節(jié)點(diǎn)判斷B是不是A的子結(jié)構(gòu)，如果不是在分別從左右兩個(gè)子樹(shù)判斷，
5    //只要有一個(gè)為true，就說(shuō)明B是A的子結(jié)構(gòu)
6    return isSub(A, B) || isSubStructure(A.left, B) || isSubStructure(A.right, B);
7}
8
9boolean isSub(TreeNode A, TreeNode B) {
10    //這里如果B為空，說(shuō)明B已經(jīng)訪問(wèn)完了，確定是A的子結(jié)構(gòu)
11    if (B == null)
12        return true;
13    //如果B不為空A為空，或者這兩個(gè)節(jié)點(diǎn)值不同，說(shuō)明B樹(shù)不是
14    //A的子結(jié)構(gòu)，直接返回false
15    if (A == null || A.val != B.val)
16        return false;
17    //當(dāng)前節(jié)點(diǎn)比較完之后還要繼續(xù)判斷左右子節(jié)點(diǎn)
18    return isSub(A.left, B.left) && isSub(A.right, B.right);
19}