题解 | #树的子结构#

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

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

    }

}
*/
import java.util.*;
public class Solution {
    boolean isSame(TreeNode root1,TreeNode root2){
        if(root2==null) return true;
        if(root1==null) return false;
        return root1.val==root2.val && isSame(root1.left,root2.left) && isSame(root1.right,root2.right);
    }
    public boolean HasSubtree(TreeNode root1,TreeNode root2) {
        if(root1==null || root2==null) return false;
//         root2和root1比 root2和root1的左子树比 root2和root1的右子树比 
        return isSame(root1,root2) || HasSubtree(root1.left,root2) || HasSubtree(root1.right,root2);
    }
}

之前思路：中序+先序 比较其遍历一次之后的string ❌ 12345 123这种就不可以 只能后序+中序 并且这种要遍历多次

层序遍历 其实和递归一样，都是遍历找root1的节点 相同，假设其为相同的根节点，进行比较， 不同就再找其子节点，如果有一样的再假设为根节点

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

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

    }

}
*/
import java.util.LinkedList;
import java.util.Queue;

public class Solution {
    public boolean isSame(TreeNode root1,TreeNode root2){
        if(root2 == null) return true;          
        if(root1 == null) return false;       
        return root1.val == root2.val
            && isSame(root1.left, root2.left)
            && isSame(root1.right, root2.right);
    }
    public boolean HasSubtree(TreeNode root1,TreeNode root2) {
        if(root1==null || root2==null) return false;
        Queue<TreeNode>q = new LinkedList<>();
        q.offer(root1);
        while(!q.isEmpty()){
            TreeNode cur = q.poll();
            if(isSame(cur,root2)) return true;
            else{
                if(cur.left!=null) q.offer(cur.left);
                if(cur.right!=null) q.offer(cur.right);
            }
            
        }
        return false;
    }
}