c语言-数据结构-沿顺相同树解决对称二叉树问题的两种思路

二叉树OJ

• 前言
• 对称二叉树

前言

本篇继续讲解二叉树OJ题目之对称二叉树

对称二叉树

题目链接：https://leetcode.cn/problems/symmetric-tree/description/


该题要求比较这棵树是否对称，对称，指的是结构对称并且值也要对称，即对应节点相等，如上图示例2中，它的结构并不对称，因此不可视为对称树

再如示例1，结构对称，并且值也对称，即对称节点的值也相同，那么便可视为对称树

因为题目告知该树至少有一个节点，所以比较的自然是根节点的左右子树，那么我们可以延续判断两棵树是否相同的思路

解决该题有两种思路

我们以题目示例1的二叉树作为示例进行讲解

第一种思路：
我们将该树根节点的左子树记为p树，右子树记为q树，之后翻转p树或者q树中任意一个，得到新的p树或q树，最后比较p树和q树是否相等即可

翻转p树后如图所示：

此时我们比较p树和q树是否相同即可，若为相同树，则原二叉树为对称树，若不为相同树则否
代码实现：

/** * Definition for a binary tree node. * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * }; */bool isSameTree(struct TreeNode* p,struct TreeNode* q){ if(p == NULL && q == NULL) { return true; } else if(p == NULL) { return false; } else if(q == NULL) { return false; } else if(p->val != q->val) { return false; } return isSameTree(p->left,q->left) && isSameTree(p->right,q->right);}void invertTree(struct TreeNode* root){ if(root == NULL) { return; } struct TreeNode* tmp = root->left; root->left = root->right; root->right = tmp; invertTree(root->left); invertTree(root->right);}bool isSymmetric(struct TreeNode* root) { invertTree(root->left); return isSameTree(root->left,root->right);}

第二种思路：
我们将该树根节点的左子树记为p树，右子树记为q树，之后比较p树和q树是否对称即可

如第一种思路，我们是将p树q树中的一个翻转后比较是否相同，而该思路则是省去翻转的步骤，直接比较结构是否对称，对称点的值是否相等

例如，我们比较p、q两树的根节点是否存在且值相同，若不存在直接返回true，代表该树对称，因为根节点的左右子树均为空；若存在且值相同，则继续往下执行

此时我们调用的判断相同树的函数，唯一不同的一点是我们在该函数中传参时传的是p树的左子树和q树的右子树比较，以及p树的右子树和q树的左子树比较

如果p树左子树与q树的右子树相同，说明外侧是对称的

如果p树右子树和q树的左子树相同，说明内侧是对称的

因此，当p树的左子树和q树的右子树相同并且p树的右子树和q树的左子树也相同时，我们可以说该二叉树是一棵对称树

代码实现：

/** * Definition for a binary tree node. * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * }; */bool isSameTree(struct TreeNode* p,struct TreeNode* q){ if(p == NULL && q == NULL) { return true; } else if(p == NULL) { return false; } else if(q == NULL) { return false; } else if(p->val != q->val) { return false; } return isSameTree(p->left,q->right) && isSameTree(p->right,q->left);}bool isSymmetric(struct TreeNode* root) { return isSameTree(root->left,root->right);}