N17_判断树B是不是树A的子结构

落日映苍穹つ 2023-08-17 17:36 96阅读 0赞

## 题目描述 ##

输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）

package new_offer;
    /**
     * 输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）
     * 判断2是不是1的子结构
     * 此题我有一个没有考虑到的地方：以为只要两个节点相同就可以了
     * （节点是引用类型 不可以如此判断 需要将节点所包含的值及节点的子树的各个值进行比较）
     * @author Sonya
     *
     */
    /**
    public class TreeNode {
        int val = 0;
        TreeNode left = null;
        TreeNode right = null;
    
        public TreeNode(int val) {
            this.val = val;
    
        }
    
    }
    */
    public class N17_HasSubtree {
    	
    	
    	    public boolean HasSubtree(TreeNode root1,TreeNode root2) {
    	    	boolean r=false;
    	    	if(root2==null) return false;
    	    	if(root1==null) return false;
    	        if(root1.val==root2.val) {
    	        	r=judege1of2(root1,root2);
    	        	}//如果有一个节点对应上  就继续判断下面是否都是满足的
    	        else if(root1.left!=null){
    	        	r=HasSubtree(root1.left,root2);
    	        }
    	        else {
    	        	r= HasSubtree(root1.right,root2);
    	        }
    	        return r;  	
    	    }
    	
    	public static boolean judege1of2(TreeNode node1, TreeNode node2) {
            if (node2 == null) {
                return true;
            }
            if (node1 == null) {
                return false;
            }
            //如果其中有一个点没有对应上，返回false
            if (node1.val != node2.val) {  
                    return false;
            }   
            //如果根节点对应的上，那么就分别去子节点里面匹配
            return judege1of2(node1.left,node2.left) && judege1of2(node1.right,node2.right);
        }
    
    
    	public static void main(String[] args) {
    		// TODO Auto-generated method stub
    		TreeNode t1,t2,t3,t4,t5,t6;
    		t1=new TreeNode(1);t2=new TreeNode(2);t3=new TreeNode(3);
    		t4=new TreeNode(4);t5=new TreeNode(5);t6=new TreeNode(6);
    		t1.left=t2;t1.right=t3;
    		t2.left=t4;t2.right=t5;
    		t3.left=t3.right=null;
    		t4.left=t6;t4.right=null;
    		t5.left=t5.right=null;
    		t6.left=t6.right=null;
    		TreeNode s1,s2,s3;
    		s1=new TreeNode(2);s2=new TreeNode(4);s3=new TreeNode(5);
    		N17_HasSubtree n17=new N17_HasSubtree();
    		boolean b1;
    		b1=n17.HasSubtree(t2, s1);
    		System.out.println(b1);
    		
          
    	}
    
    }

转载于:https://www.cnblogs.com/kexiblog/p/11083184.html