輸入兩棵二叉樹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
限制：

代碼：

/**

?*?Definition?for?a?binary?tree?node.

?*?public?class?TreeNode?{

?*?????int?val;

?*?????TreeNode?left;

?*?????TreeNode?right;

?*?????TreeNode(int?x)?{?val?=?x;?}

?*?}

?*/

class?Solution?{

????public?boolean?isSubStructure(TreeNode?A,?TreeNode?B)?{

????????if(A==null?&&?B==null)?return?true;

????????if(A==null)

????????{

????????????return?false;

????????}

????????if(B==null)

????????{

????????????return?false;

????????}

????????if(find(A,B))

????????{

????????????return?true;

????????}

????????if(isSubStructure(A.left,B))

????????{

????????????return?true;

????????}

????????if(isSubStructure(A.right,B))

????????{

????????????return?true;

????????}

????????return?false;

????}

????public?boolean?find(TreeNode?A,TreeNode?B)

????{

????????if(A==null&&B==null)

????????{

????????????return?true;

????????}

????????if(A==null)

????????{

????????????return?false;

????????}

????????if(B==null)

????????{

????????????return?true;

????????}

????????if(A.val==B.val)

????????{

????????????return?find(A.left,B.left)&&find(A.right,B.right);

????????}

????????else

????????{

????????????return?false;

????????}

???????//?return?true;

????}

}

總結

以上是生活随笔為你收集整理的【剑指offer】面试题26：树的子结构（Java）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。