题解 | #树的子结构#

//遍历root1树的节点root，当节点值等于root2时
//判断root与root2是否相同
//判断root的左子节点与root2的左子节点
//有不等返回false
//递归判断root.left
//判断root的右子节点与root2的右子节点
//有不等返回false
//递归判断root.left

import java.util.*;

public class Solution {
    public boolean HasSubtree(TreeNode root1,TreeNode root2) {
        if(root1==null||root2==null){
            return false;
        }
        LinkedList<TreeNode> Nodearray = new LinkedList();
        LinkedList<TreeNode> Node = new LinkedList();
        Node.add(root1);
        //层序遍历原树
        while(Node.size()!=0){
            TreeNode node = Node.poll();
            Nodearray.add(node);
            if(node.left!=null){
                Node.add(node.left);
            }
            if(node.right!=null){
                Node.add(node.right);
            }
        }
        //逐个节点判断
        for(int i=0;i<Nodearray.size();i++){
                if(equalTree(Nodearray.get(i),root2)){
                    return true;
                }
        }
        return false;

        //遍历root1树的节点root，当节点值等于root2时
        //判断root与root2是否相同
        //判断root的左子节点与root2的左子节点
        //有不等返回false
        //递归判断root.left
        //判断root的右子节点与root2的右子节点
        //有不等返回false
        //递归判断root.left
    }

    public boolean equalTree(TreeNode root1,TreeNode root2){
        if(root1.val!=root2.val){
            return false;
        }

        if((root1.left!=null&&root2.left!=null)&&!equalTree(root1.left,root2.left)){
            //二者均有左子结构
            //同时如果左子节点结构不相同则直接返回false
            //否则判断右子结构的情况
                return false;
        }else if((root1.left==null&&root2.left!=null)){//当root1 无子结构时，若root2 有子结构则 返回false
            return false;
        }
        if((root1.right!=null&&root2.right!=null)&&!equalTree(root1.right,root2.right)){
                return false;
        }else if((root1.right==null&&root2.right!=null)){
            return false;
        }
        //子结构均相同返回true

        return true;
    }
}