C++ 推断一棵二叉树是否对称

一棵二叉树对称，就是说它假设以根为轴，翻转过去一样。例如以下图所看到的，以虚线为轴。把左边翻转到右边，各顶点及顶点中的值一一相应。

watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvT3J0aG9jZW50ZXJDaG9jb2xhdGU=/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/SouthEast" alt="">

注意，它并不要求单独看子树的时候子树也是对称的，例如以下图，单独看左子树时，左子树是不正确称的，单独看右子树时。右子树也是不正确称的，但这棵本身是对称的。

watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvT3J0aG9jZW50ZXJDaG9jb2xhdGU=/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/SouthEast" alt="">

要推断一棵二叉树是否对称，那就是推断它的左子树翻转过去是否和右子树一样，注意这里的“一样”包含了值也一样。

以下给出代码，当中的样例中的树，就是第一张图中的那棵树：

#include <iostream>

using namespace std;

 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==NULL)//假设树为空，对称。返回

			return true;

		return mySymmetric(root->left,root->right);//否则推断以root为根时。左子树翻转后是否和右子树一样

    }

	bool mySymmetric(TreeNode *leftChild,TreeNode *rightChild) {

		if(leftChild==NULL && rightChild==NULL)//左右子树都为空，对称

			return true;

		else if(leftChild!=NULL && rightChild==NULL || leftChild==NULL && rightChild!=NULL){//一个空一个非空，则不正确称

			return false;

		}else{

		//否则，再推断

			if(mySymmetric(leftChild->left,rightChild->right) //（1）leftChild的左子树和rightChild的右子树对称吗？

				&& mySymmetric(leftChild->right,rightChild->left) //（2）leftChild的右子树和rightChild的左子树对称吗？

				&& leftChild->val==rightChild->val){ //（3）leftChild和rightChild的值一样吗？

					return true;//三个条件都满足，对称

			}else

				return false;//否则不正确称

		}

    }

};

int main()

{

	//样例

	TreeNode root(1);

	TreeNode leftChild(2);

	TreeNode rightChild(2);

	TreeNode leftLeftChild(3);

	TreeNode leftRightChild(4);

	TreeNode rightLeftChild(4);

	TreeNode rightRightChild(3);

	root.left=&leftChild;

	root.right=&rightChild;

	leftChild.left=&leftLeftChild;

	leftChild.right=&leftRightChild;

	rightChild.left=&rightLeftChild;

	rightChild.right=&rightRightChild;

	Solution s;

	if(true==s.isSymmetric(&root))

		cout<<"对称"<<endl;

	else

		cout<<"不正确称"<<endl;

	system("pause");

	return 0;

}

以下通过几个简单的图来说明一下。

mySymmetric(leftChild->left,rightChild->right)是计算下图中蓝色方框的部分是否关于对称轴对称：

watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvT3J0aG9jZW50ZXJDaG9jb2xhdGU=/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/SouthEast" alt="">

      mySymmetric(leftChild->right,rightChild->left)是计算下图中蓝色方框的部分是否关于对称轴对称：

watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvT3J0aG9jZW50ZXJDaG9jb2xhdGU=/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/SouthEast" alt="">

别忘了还要比較它们的值是否相等~

C++ 推断一棵二叉树是否对称的相关教程结束。