今天我们一起来看一道判断一棵树是否为对称二叉树的题,力扣101题,
https://leetcode.cn/problems/symmetric-tree/
我们首先先来分析这道题,要判断这道题是否对称,我们首先需要判断的是这颗树根节点的左右子树是否对称,所以我们比较对象是根节点的左右子树,那我们不妨自己写一个函数my_isSymmetric,参数就是
bool my_isSymmetric(struct TreeNode* leftroot,struct TreeNode* rightroot),我们用这个函数来判断这棵树的左右子树是否对称,首先我们要判断如果
左右子树都是空树呢?也就是这棵树只有一个根节点,这样的话也还算对称的,即
if(leftroot==NULL&&rightroot==NULL){return true;}
左右子树都为空的情况判断了,现在判断有一边为空的情况呢?肯定就不对称了,即
if(leftroot==NULL||rightroot==NULL){return false;}
有人会疑问为什么这里的连接符号用||,注意,程序走到这里的前提是这棵树的左右子树不为空,即左右子树两边不会同时为空,所以用||符号如果leftroot==NULL就不会走后面rightroot==NULL,如果leftroot!=NULL,走到后面判断right==NULL是否为空,如果两边有一边为空,这棵树肯定就不对称返回false;
下面,程序走过上面那一步那就证明左右子树都不为空,那我们只需要判断leftroot的val和rightroot的val是否相等就可以了,如果不相等返回false,即
if(leftroot->val!=rightroot->val){return false;}
这个时候程序还没有返回,那就是上述步骤都顺利通过,那就递归判断leftroot的左子树和righttoor的右子树 和 leftroot的右子树和right的左子树是否相等就可以了,
即
return my_isSymmetric(leftroot->left,rightroot->right)&&my_isSymmetric(leftroot->right,rightroot->left);
这个函数到这里就封装完毕了,我们只需要在给的isSymmetric下面调用自己的my_isSymmetric就可以啦,即
return my_isSymmetric(root->left,root->right);
完整代码
/*** Definition for a binary tree node.* struct TreeNode {* int val;* struct TreeNode *left;* struct TreeNode *right;* };*/
bool my_isSymmetric(struct TreeNode* leftroot,struct TreeNode* rightroot)
{if(leftroot==NULL&&rightroot==NULL)//判断左右子树是否都为空{return true;}if(leftroot==NULL||rightroot==NULL)//判断是由有一边为空{return false;}if(leftroot->val!=rightroot->val)//判断左右子树val是否相等{return false;}return my_isSymmetric(leftroot->left,rightroot->right)&&my_isSymmetric(leftroot->right,rightroot->left);//左子树的左子树和右子树的右子树比较,左子树的右子树和右子树的左子树比较,二者必须同时满足;}
bool isSymmetric(struct TreeNode* root) {return my_isSymmetric(root->left,root->right);
}