Same Tree--LeetCode

朴灿烈づ我的快乐病毒、 2022-08-05 14:19 103阅读 0赞

# 题目： #

Given two binary trees, write a function to check if they are equal or not.

Two binary trees are considered equal if they are structurally identical and the nodes have the same value.

思路：使用递归，如果不使用递归，也可以按照相同的遍历方法，记录遍历的节点，比较两个遍历的节点

bool SameTree(BinTree* first,BinTree* second)
    {
    	if(first==NULL && second == NULL)
    		return true;
    	else if(first != NULL && second == NULL)
    		return false;
    	else if(first == NULL && second !=NULL)
    		return false;
    	else
    	{
    		if(first->value != second->value)
    			return false;
    		else
    			return SameTree(first->left,second->left)&&SameTree(first->right,second->right);
    	}
    }

不使用递归也是可以解决问题的，可以考虑使用层次遍历的方法，层次遍历方法比较两个树是否相同。

bool SameTree(BinTree* first,BinTree* second)
    {
    	deque<BinTree*> vec;
    	deque<BinTree*> sec;
    	int i;
    	vec.push_back(first);
    	sec.push_back(second);
    	BinTree* temp,*temp1 ;
    	while(!vec.empty() && !sec.empty())
    	{
    		temp = vec.front();
    		vec.pop_front();
    		temp1 = sec.front();
    		sec.pop_front();
    		if(temp != NULL && temp1 != NULL && temp->value == temp1->value)
    		{
    			
    			if(temp->left != NULL)
    				vec.push_back(temp->left);
    			else if(temp1->left != NULL)
    				return false;
    			if(temp->right != NULL)
    				vec.push_back(temp->right);
    			else if(temp1->right != NULL)
    				return false;
    			if(temp1->left != NULL)
    				sec.push_back(temp1->left);
    			else if(temp->left != NULL)
    				return false;
    			if(temp1->right != NULL)
    				sec.push_back(temp1->right);
    			else if(temp->right != NULL)
    				return false;
    				
    		}
    		else
    			return false;
    	}
    	if(!vec.empty() || !sec.empty())
    		return false;
    	return true;
    }