首页 > 代码库 > leetcode 之 Symmetric Tree 镜像树

leetcode 之 Symmetric Tree 镜像树

Symmetric Tree


Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).

For example, this binary tree is symmetric:

    1
   /   2   2
 / \ / 3  4 4  3

But the following is not:

    1
   /   2   2
   \      3    3
递归解法:由于对称性,每次把一个节点的左子树和它兄弟节点的左子树进行比较,然后递归处理即可。
struct TreeNode {
     int val;
     TreeNode *left;
     TreeNode *right;
     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Solution {
public:
bool isSymmetricRecursive(TreeNode* root1,TreeNode* root2)
{
	if(root1 == NULL && root2 == NULL)return true;
	if(root1 == NULL || root2 == NULL)return false;
	return (root1->val == root2->val) && isSymmetricRecursive(root1->left,root2->right) && isSymmetricRecursive(root1->right,root2->left);

}
    bool isSymmetric(TreeNode *root) {
        if(root == NULL)return true;
	return isSymmetricRecursive(root->left,root->right);
    }
};


迭代方法:思路和递归一样,此处使用两个队列进行处理,把左子树的孩子放入第一个队列,右子树的放入第二个队列,每次取队首元素进行判断,速度比递归快了几倍
struct TreeNode {
     int val;
     TreeNode *left;
     TreeNode *right;
     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Solution {
public:
    bool isSymmetric(TreeNode *root) {//判断镜像树和生成镜像树不同
    	if(!root || !root->left && !root->right)return true;
    	queue<TreeNode*> leftQueue,rightQueue;
    	leftQueue.push(root->left);
    	rightQueue.push(root->right);
    	while(leftQueue.size() > 0 && rightQueue.size() > 0)
    	{
    		TreeNode* pNode1 = leftQueue.front();
    		leftQueue.pop();
    		TreeNode* pNode2 = rightQueue.front();
    		rightQueue.pop();
    		if(!pNode1 && !pNode2)continue;//都为空
    		if(!pNode1 || !pNode2)return false;//只有一个为空
    		if(pNode1->val != pNode2->val)return false;//都不为空
    		leftQueue.push(pNode1->left),leftQueue.push(pNode1->right);//第一个队列先进左子树
    		rightQueue.push(pNode2->right),rightQueue.push(pNode2->left);//第二个队列先进右子树
    	}
    	if(leftQueue.size() > 0 || rightQueue.size() > 0)return false;
    	return true;
    }
};


剑指offer之镜像树 
题目:输入一颗二元查找树,将该树转换为它的镜像,即在转换后的二元查找树中,左子树的结点都大于右子树的结点。用递归和循环两种方法完成树的镜像转换。
分析:这里是转换为镜像树,思路和上面的判断类似,每次分别处理左右子树,可以使用递归,也可以使用迭代。此处和判断不同的地方在于,判断必须定位到每个节点的镜像节点的位置,而转换由于不需要一步转换完成,所以每个节点之需要和相邻节点进行交换,相对还比较简单一点。对于迭代,可以使用队列,也可以使用堆栈,具体代码如下:
struct TreeNode {
     int val;
     TreeNode *left;
     TreeNode *right;
     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

void SymmetricTreeRecursive(TreeNode* root)//递归,注意和上面判断镜像树的区别
{
	if(!root)return;
	TreeNode* tmp = root -> left;
	root -> left = root->right;
	root->right = tmp;
	SymmetricTreeRecursive(root->left);
	SymmetricTreeRecursive(root->right);
}

void SymmetricTreeIterative(TreeNode* root)//迭代
{
	if(!root)return;
	stack<TreeNode*> s;
	s.push(root);
	while(!s.empty())
	{
		TreeNode* pCur = s.top();
		s.pop();
		TreeNode* tmp = pCur->left;
		pCur->left = pCur->right;
		pCur->right = tmp;
		if(pCur->left)s.push(pCur->left);
		if(pCur->right)s.push(pCur->right);
	}
}

Same Tree

 

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.

递归解法

struct TreeNode {
     int val;
     TreeNode *left;
     TreeNode *right;
     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Solution {
public:
    bool isSameTree(TreeNode *p, TreeNode *q) {
        if(p == NULL && q == NULL)return true;
	if(p == NULL || q == NULL)return false;
	if(p->val == q->val)return isSameTree(p->left,q->left) && isSameTree(p->right,q->right);
	else return false;
    }
};


迭代解法(和上面类似),比递归算法高了7倍

struct TreeNode {
     int val;
     TreeNode *left;
     TreeNode *right;
     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Solution {
public:
    bool isSameTree(TreeNode *p, TreeNode *q) {
    	if(!p && !q)return true;
    	if(!p || !q)return false;
    	queue<TreeNode*> queue1,queue2;
    	queue1.push(p),queue2.push(q);
    	while(queue1.size()>0 && queue2.size()>0)
    	{
    		TreeNode* pNode1 = queue1.front(),*pNode2 = queue2.front();
    		queue1.pop(),queue2.pop();
    		if(!pNode1 && !pNode2)continue;
    		if(!pNode1 || !pNode2)return false;
    		if(pNode1->val != pNode2->val)return false;
    		queue1.push(pNode1->left),queue1.push(pNode1->right);
    		queue2.push(pNode2->left),queue2.push(pNode2->right);//由于是判断相同树,所以进队顺序相同
    	}
    	if(queue1.size()>0 || queue2.size()>0)return false;
    	return true;
    }
};



leetcode 之 Symmetric Tree 镜像树