子樹和子結構的區別

這棵大樹的子樹有：

• 4 和 5 對應的兩棵子樹
• 3 本身自己完整的一棵樹

而里面的小框圈出來的不是 3 這棵大樹的子樹！

還是上面那張圖，子結構就是不用那么嚴格，圖中的小框就是整棵樹的子結構，圖中的黃色大框也是整棵樹的子結構，所以只要找到符合樹的一部分樹結點即可

思路：首先遍歷大樹，找到與小樹根結點相同值的節點，然后判斷以該節點為根結點的樹是否與小樹相同，如果不同，則繼續遍歷大樹的左右子樹是否相同，在找到一個與小樹根結點值相同的節點。判斷兩個樹是否相同時，當小樹遍歷完后，說明有子結構，當根樹遍歷完后，說明還沒有找到與小樹某個節點相同的節點，則不包含子結構。

/**
public class TreeNode {
? ? int val = 0;
? ? TreeNode left = null;
? ? TreeNode right = null;

? ? public TreeNode(int val) {
? ? ? ? this.val = val;

? ? }

}
*/
public class Solution {
? ? public boolean HasSubtree(TreeNode root1,TreeNode root2) {
? ? ? ? if(root1==null||root2==null){
? ? ? ? ? ? return false;
? ? ? ? }
? ? ? ? if(root1.val==root2.val){
? ? ? ? ? ? if(judge(root1,root2)){
? ? ? ? ? ? ? ? return true;
? ? ? ? ? ? }
? ? ? ? }
? ? ? ? return HasSubtree(root1.left,root2)||HasSubtree(root1.right,root2);
? ? }
? ? boolean judge(TreeNode root,TreeNode subtree){
? ? ? ? if(subtree==null){
? ? ? ? ? ? return true;
? ? ? ? }
? ? ? ? if(root==null){
? ? ? ? ? ? return false;
? ? ? ? }
? ? ? ? if(root.val==subtree.val){
? ? ? ? ? ? return judge(root.left,subtree.left)&&judge(root.right,subtree.right);
? ? ? ? }
? ? ? ? return false;
? ? }
}

總結

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

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