題目
輸入兩棵二叉樹A和B，判斷B是不是A的子結構。(約定空樹不是任意一個樹的子結構)
B是A的子結構， 即 A中有出現和B相同的結構和節點值。
例如:
給定的樹 A:
? ? ?3
? ? / \
? ?4 ? 5
? / \
?1 ? 2
給定的樹 B：
? ?4?
? /
?1
返回 true，因為 B 與 A 的一個子樹擁有相同的結構和節點值。
示例 1：
輸入：A = [1,2,3], B = [3,1]
輸出：false
示例 2：
輸入：A = [3,4,5,1,2], B = [4,1]
輸出：true
限制：
0 <= 節點個數 <= 10000
解題思路
1.題目要求我們判斷B是不是A的子結構，我們用遞歸來解決這個問題。
2.二叉樹 B 為 A 的子結構的情況一共有三種，滿足其中一種即可：
①子結構 B 的起點為 A 的根節點，即從 A 的根節點開始和 B 比較， 調用函數 isSubStree:
- 不相等，則返回 false;
- 相等，則再比較 左子樹和右子樹都是否相等，都相等，才返回 true
②子結構 B 在 A 的左子樹中，即 B 的起點隱藏在 A 的左子樹中，此時調用函數 isSubStructure；
③子結構 B 在 A 的右子樹中，即 B 的起點隱藏在 A 的右子樹中，此時調用函數 isSubStructure。3.舉個例子：
我們先從 A 的根節點開始和 B 比較，調用函數 isSubStree:
根節點相等，則再比較 左子樹和右子樹都是否相等，都不1相等，返回 false。
?我們猜測子結構 B 在 A 的左子樹中，即 B 的起點隱藏在 A 的左子樹中，此時調用函數 isSubStructure
?在左子樹中調用函數 isSubStree，根節點都不同則返回 false;再往左子樹走，
?依舊不同，此時我們返回上一級，去看看右子樹
也不同，此時A的左子樹全部檢索完畢，我們需要檢索右子樹
?這時我們調用函數 isSubStree，根節點相等，則再比較 左子樹和右子樹都是否相等，都相等，返回 true。代表我們找到了子結構。
?
代碼實現
lass Solution {public boolean isSubStructure(TreeNode A, TreeNode B) {if(A == null || B == null){return false;}if(isSubTree(A, B)){return true;}if(isSubStructure(A.left, B) || isSubStructure(A.right, B)){return true;}return false;}boolean isSubTree(TreeNode TA, TreeNode TB){if(TB == null){return true;}if(TA == null){return false;}if(TB.val != TA.val){return false;}return isSubTree(TA.left , TB.left) &&isSubTree(TA.right, TB.right);}}測試結果
?
