问题描述:给定两个二叉树,编写一个函数来检验他们是否相同。如果两个树在结构上相同,并且节点具有相同的值,则认为他们是相同的。
递归方式求解:传入两个树相同的节点,若两者相同则同时进入左子树和右子树。
public Boolean isSame(TreeNode root1,TreeNode root2)
{
if(root1==null&&root2==null){return true;}
if((roo1==null&&root2!=null)||(roo1!=null&&root2==null)){return false;}
if(root1.val!=root2.val){return false;}
return isSame(root1.left,root2.left)&&isSame(roo1.right,root2.right);
}
?
非递归的方式求解:采用BFS的方法求解,定义两个queue分别记录root1的节点和root2的点,并在加入队列过程中对于结构进行判断。
public Boolean isSame(TreeNode root1,TreeNode root2)
{
if(root1==null&&root2==null){return true;}
if((roo1==null&&root2!=null)||(roo1!=null&&root2==null)){return false;}
Queue<Integer>queue1=new LinkedList<TreeNode>();
Queue<Integer>queue2=new LinkedList<TreeNode>();
queue1.add(root1);
queue2.add(root2);
while(!queue1.isEmpty()||!queue2.isEmpty())
{
int queueSize=queue1.size();
for(int i=0;i<queueSize;i++)
{
TreeNode queueNode1=queue1.poll();
TreeNode queueNode2=queue2.poll();
if(queueNode1.val!=queueNode2.val){return false;}
if((queueNode1.left==null&&queueNode2.left!=null)||(queueNode1.left!=null&&queueNode2.left==null)){return false;}
if((queueNode1.right==null&&queueNode2.right!=null)||(queueNode1.right!=null&&queueNode2.right==null)){return false;}
if(queueNode1.left!=null)
{
queueNode1.add(queueNode1.left);
queueNode2.add(queueNode2.left);
}
if(queueNode1.right!=null)
{
queueNode1.add(queueNode1.right);
queueNode2.add(queueNode2.right);
}
}
}
return? true;
}