树的子结构

问题描述

输入两颗二叉树A，B，判断B是不是A的子结构

思路分析

要在原二叉树中查找是否具有某棵子树，只需要判断每个节点是否都在二叉树中是否出现即可。所以需要先判断头结点，只有头结点符合要求才继续比较其子树是否符合，然后在从左右子树依次比较，如果都符合，则说明B是A的子树

码上有戏

public class TreeNode{
		int data;
		TreeNode left;
		TreeNode right;
		
		TreeNode(int data){
			this.data=data;
		}
	}
	
	public boolean HasSubtree(TreeNode root1,TreeNode root2){
		boolean hasSubTree=false;
		if(root1!=null&&root2!=null)
		{
			if(root1.data==root2.data)
			{
				hasSubTree=nodesValEqual(root1,root2);
			}
			if(!hasSubTree)
			{
				hasSubTree=HasSubtree(root1.left,root2.left);
			}
			if(!hasSubTree)
			{
				hasSubTree=HasSubtree(root1.right,root2.right);
			}
		}
		return hasSubTree;
	}
	
	private boolean nodesValEqual(TreeNode root1,TreeNode root2){
		if(root2==null)
			return true;
		if(root1==null)
			return false;
		if(root1.data!=root2.data)
			return false;
		return nodesValEqual(root1.left,root2.left)&&nodesValEqual(root1.right,root2.right);
	}
}