【剑指Offer】对称的二叉树

题目描述

请实现一个函数，用来判断一颗二叉树是不是对称的。注意，如果一个二叉树同此二叉树的镜像是同样的，定义其为对称的。

递归思路与代码

用递归的话咱们需要增加一个递归函数bool IsSym(TreeNode* lef, TreeNode* rig) ；
首先考虑出口：
（1）当lef 与rig都等于空的时候，返回true，说明二叉树搜索完了；
（2）当lef与rig只有一个是空，另外一个非空，或者lef与rig的val值不相等，都返回false，说明不对称。
下来考虑调用
（3）IsSym(lef->left, rig->right) && IsSym(lef->right, rig->left)；记住要一对一对调用。左左对右右，左右对右左。

代码：

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

class Solution {
public:
	bool IsSym(TreeNode* lef, TreeNode* rig) {
		if (lef == nullptr && rig == nullptr&&lef->val==rig->val)//出口（1）
			return true;
		if ((lef == nullptr && rig != nullptr) || (lef != nullptr && rig == nullptr)
		|| lef->val != rig->val)//出口（2）
			return false;
		return IsSym(lef->left, rig->right) && IsSym(lef->right, rig->left);
	}
	bool isSymmetrical(TreeNode* pRoot)
	{
		if (pRoot == nullptr)
			return true;
		return IsSym(pRoot->left, pRoot->right);
	}

};

非递归思路与代码

非递归有两种，第一种队列实现非递归。

队列实现非递归

给队列中每次压入成对的节点：
当队列不为空的时候
（1）若队列不为空，成对的提取和弹出。
（2）若该对lef和rig都为空，则不再压入，直接进行continue。下面这种时候出现这种情况

（3）当lef与rig只有一个是空，另外一个非空，或者lef与rig的val值不相等，都返回false，说明不对称。
下来考虑调用
（4）继续进行成对的压入左左对右右，左右对右左。
注：用队列实现，是一层一层来遍历判断的。属于BFS（广/宽度优先搜索）。
代码：

class Solution {
public:

	bool isSymmetrical(TreeNode* pRoot)
	{
		if (pRoot == nullptr)
			return true;
		queue< TreeNode*> myq;
		myq.push(pRoot->left);
		myq.push(pRoot->right);
		while (!myq.empty()) {
			TreeNode* lef = myq.front();
			myq.pop();
			TreeNode* rig = myq.front();
			myq.pop();
			if (lef == nullptr && rig == nullptr)
				continue;
			if ((lef == nullptr && rig != nullptr) || (lef != nullptr && rig == nullptr) 
			|| lef->val != rig->val)
				return false;
			myq.push(lef->left);
			myq.push(rig->right);
			myq.push(lef->right);
			myq.push(rig->left);
		}
		return true;
	}

};

栈实现非递归

给栈中每次压入成对的节点：
当栈不为空的时候
（1）若栈不为空，成对的提取和弹出。
（2）若该对lef和rig都为空，则不再压入，直接进行continue。
（3）当lef与rig只有一个是空，另外一个非空，或者lef与rig的val值不相等，都返回false，说明不对称。
下来考虑调用
（4）继续进行成对的压入左左对右右，左右对右左。
注：用栈实现，是一个支路一个支路来遍历判断的。属于DFS（广/宽度优先搜索）。
代码与队列实现的方式除了一个使用queue装，下面这个使用stack 装之外，其他代码都一样。
注：但是认真画一下二叉树看一下怎么比较判断的。这两个实现方式在比较判断的节点顺序上完全不同。

class Solution {
public:

	bool isSymmetrical(TreeNode* pRoot)
	{
		if (pRoot == nullptr)
			return true;
		stack< TreeNode*> mys;
		mys.push(pRoot->left);
		mys.push(pRoot->right);
		while (!mys.empty()) {
			TreeNode* lef = mys.top();
			mys.pop();
			TreeNode* rig = mys.top();
			mys.pop();
			if (lef == nullptr && rig == nullptr)
				continue;
			if ((lef == nullptr && rig != nullptr) || (lef != nullptr && rig == nullptr)
			 || lef->val != rig->val)
				return false;
			mys.push(lef->left);
			mys.push(rig->right);
			mys.push(lef->right);
			mys.push(rig->left);
		}
		return true;
	}

};