题目

对称二叉树判断

题目要求

题目链接

示例

解答

方法一、

递归法

实现思路

使用到了判断两棵二叉树是否相等的方法，只不过对称二叉树判断的是p结点的左孩子和q结点的右孩子，p结点的右孩子和q结点的左孩子是否相等。

时间复杂度和空间复杂度

时间复杂度：O(N)
空间复杂度：O(N)

代码

 bool isSameTree(struct TreeNode* p, struct TreeNode* q){if(p==NULL&&q==NULL){return true;}if(p==NULL||q==NULL){return false;}if(p->val!=q->val){return false;}//和判断两个二叉树相等类似，不过判断的是p结点的左孩子和q结点的右孩子是否相等//还判断p结点的右孩子和q结点的左孩子是否相等，因为对称为镜像，所以需要这样比较。return isSameTree(p->left,q->right)&&isSameTree(p->right,q->left);}
bool isSymmetric(struct TreeNode* root){//如果二叉树为空，则返回trueif(root==NULL){return true;}return isSameTree(root->left,root->right);
}

方法二、

实现思路

时间复杂度和空间复杂度

代码