輸入兩棵二叉樹A和B个绍，判斷B是不是A的子結(jié)構(gòu)。(約定空樹不是任意一個樹的子結(jié)構(gòu))
B是A的子結(jié)構(gòu)， 即 A中有出現(xiàn)和B相同的結(jié)構(gòu)和節(jié)點值币喧。
思路：采用雙遞歸的方式，外層遞歸在二叉樹A中找到與二叉樹B的root節(jié)點相同的節(jié)點袱耽，內(nèi)層遞歸則是從第一個相同節(jié)點開始進行相同方向的遍歷操作
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
public boolean isSubStructure(TreeNode A, TreeNode B) {
if (A == null || B == null) {
return false;
}
// 這里使用或運算杀餐，當?shù)谝粋€條件不滿足的時候執(zhí)行第二個條件，當?shù)诙€條件不滿足的時候執(zhí)行第三個條件
// 當三個條件都為false的時候朱巨，才返回false
// 第一個條件是判斷當前節(jié)點是否相同史翘，如果不相同，則返回false
// 第一個條件不滿足時，沿著主樹A的左子樹開始遍歷查詢琼讽，進行遞歸必峰，直到找到與B的root節(jié)點相同的點
// 如果第二個條件不滿足，說明在A的左子樹中也沒有找到與B的root節(jié)點相同的點钻蹬，則遍歷A的右子樹
return isSubtreeWithRoot(A, B) || isSubStructure(A.left, B) || isSubStructure(A.right, B);
}
public boolean isSubtreeWithRoot(TreeNode A, TreeNode B) {
// 說明B已經(jīng)遍歷完成吼蚁，則直接返回true
if (B == null) {
return true;
}
if (A == null) {
return false;
}
// 找到當前節(jié)點相同的，如果當前節(jié)點不相同问欠，則返回false
if (A.val != B.val) {
return false;
}
// 這里采用與運算肝匆，即需要兩個方向同時進行遍歷相同
return isSubtreeWithRoot(A.left, B.left) && isSubtreeWithRoot(A.right, B.right);
}
