例题-对称的二叉树

题目描述

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

原理

对于一棵二叉树，从根结点开始遍历，

如果左右子结点有一个为NULL，那么肯定不是对称二叉树；

如果左右子结点均不为空，但不相等，那么肯定不是对称二叉树；

如果左右子结点均不为空且相等，那么

遍历左子树，遍历顺序为：当前结点，左子树，右子树；

遍历右子树，遍历顺序为：当前结点，右子树，左子树；

如果遍历左子树的序列和遍历右子树的序列一样，那么该二叉树为对称的二叉树。（递归实现）

代码实现

class TreeNode 
{
public:
	int data;
	TreeNode* lchild = nullptr;
	TreeNode* rchild = nullptr;
	TreeNode(int data) :data(data) {};
	~TreeNode() {};
};

class Tree
{
public:
	bool isSame(TreeNode* first, TreeNode* second) 
	{//判断是否相同 
    	if (!first && !second)
    		return true;
    	if (!first || !second)
    		return false;
    	if (first->data != second->data)
    		return false;
    	return isSame(first->lchild, second->rchild) && isSame(first->rchild, second->lchild);
    }
	bool isSymmetrical(TreeNode* pRoot)
	{//判断是否对称
    	if (pRoot == nullptr)
    		return true;
    	return isSame(pRoot->lchild, pRoot->rchild);
	}
};

例子1

输入为

{8,6,6,5,7,7,5}

输出为

true

例子2

输入为

{8,6,9,5,7,7,5}

输出为

false