数据结构 ——— 链式二叉树oj题：对称二叉树

目录

题目要求

手搓一个对称二叉树

代码实现 

题目要求

给你一个二叉树的根节点 root ， 检查它是否轴对称

手搓一个对称二叉树

代码演示：

// 数据类型
typedef int BTDataType;
 
// 二叉树节点的结构
typedef struct BinaryTreeNode
{
	BTDataType data; //每个节点的数据
 
	struct BinaryTreeNode* left; //指向左子树的指针
 
	struct BinaryTreeNode* right; //指向右子树的指针
}BTNode;
 
// 申请新节点
BTNode* BuyNode(BTDataType x)
{
	BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));
 
	// 判断是否申请成功
	if (newnode == NULL)
	{
		perror("malloc fail");
		return NULL;
	}
 
	// 初始化
	newnode->data = x;
	newnode->left = NULL;
	newnode->right = NULL;
 
	return newnode;
}
 
BTNode* CreatBinaryTree1()
{
	BTNode* n1 = BuyNode(1);
    assert(n1);
    BTNode* n2 = BuyNode(2);
    assert(n2);
    BTNode* n3 = BuyNode(3);
    assert(n3);
    BTNode* n4 = BuyNode(2);
    assert(n4);
    BTNode* n5 = BuyNode(4);
    assert(n5);
    BTNode* n6 = BuyNode(3);
    assert(n6);
    BTNode* n7 = BuyNode(4);
    assert(n7);
	
	n1->left = n2;
	n1->right = n4;
	n2->left = n3;
	n4->left = n5;
	n4->right = n6;
	n2->right = n7;

	return n1;
}

代码实现

代码演示：

bool _isSymmetric(BTNode* leftRoot, BTNode* rightRoot)
{
	if (leftRoot == NULL && rightRoot == NULL)
		return true;

	if (leftRoot == NULL || rightRoot == NULL)
		return false;

	if (leftRoot->data != rightRoot->data)
		return false;

	return _isSymmetric(leftRoot->left, rightRoot->right) && _isSymmetric(leftRoot->right, rightRoot->left);
}
bool isSymmetric(BTNode* root)
{
	if (root == NULL)
		return true;

	return _isSymmetric(root->left, root->right);
}

代码解析：

要判断一棵树是否是对称二叉树，那么就要让左右子树同时走，才能判断，也就是要有左右子树两个参数才能判断，所以 isSymmetric 这个函数不能满足要求，需要再定义一个子函数 _isSymmetric 来判断是否对称
第一个 if 语句用于判断两个 root 是否为空，并且和下面的其他 if 语句是相辅相成的，如果下面的 if 语句都没有返回的 false 的话，那么两个 root 同时走到空了就说明对应节点是对称的
第二三个 if 语句用于排除非对称的情况，返回 false
最后再递归两个 root 的左右子树，并且用逻辑与关联，只有一方不为 true ，那么就说明不对称，另一方就不用再递归下去

代码验证：

当树是对称二叉树时：

当树不是对称二叉树时：