115 递归和非递归两种方式解相同的树

发布时间:2024年01月17日

问题描述:给定两个二叉树,编写一个函数来检验他们是否相同。如果两个树在结构上相同,并且节点具有相同的值,则认为他们是相同的。

递归方式求解:传入两个树相同的节点,若两者相同则同时进入左子树和右子树。

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;
}

文章来源:https://blog.csdn.net/qq_52299902/article/details/135654663
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。