101. 对称二叉树【 力扣(LeetCode) 】

零、原题链接

101. 对称二叉树

一、题目描述

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

进阶：你可以运用递归和迭代两种方法解决这个问题吗？

二、测试用例

示例 1：

输入：root = [1,2,2,3,4,4,3]
输出：true

示例 2：

输入：root = [1,2,2,null,3,null,3]
输出：false

提示：

树中节点数目在范围 [1, 1000] 内
-100 <= Node.val <= 100

三、解题思路

3.1 递归

1. 基本思路：
     递归，比较对称位置的结点是否相同即可
2. 具体思路：
   • 左子树结点和右子树结点有一个为空，另一个非空，则不轴对称；
   • 两个都是空，则轴对称；
   • 两个都不为空：
     • 值相同，则判断 左子树的左子树 和 右子树的右子树 是否轴对称 且 左子树的右子树 和 右子树的左子树 是否轴对称；
     • 值不同，则不是轴对称；

3.2 迭代

1. 基本思路：
     迭代，用栈实现递归，还是比较对称位置的结点是否相同即可
2. 具体思路：
   • 将左右子树入栈；
   • 只要栈非空：
     • 弹出两个元素，比较是否相同：
       • 相同，非空的话，将他们的左右子树间隔入栈，且顺序相反，即一个左右，一个右左；
       • 不相同，则不是轴对称；
   • 栈空，则表示是轴对称；

四、参考代码

4.1 递归

时间复杂度：$\mathrm{O}(n)$
空间复杂度：$\mathrm{O}(logn)$

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left),* right(right) {}* };*/
class Solution {
public:bool isSymmetric(TreeNode* left, TreeNode* right) {if ((left == nullptr) ^ (right == nullptr))return false;else if (left == nullptr)return true;else {if (left->val == right->val)return isSymmetric(left->left, right->right) &&isSymmetric(left->right, right->left);elsereturn false;}}bool isSymmetric(TreeNode* root) {return isSymmetric(root->left, root->right);}
};

4.2 迭代

时间复杂度：$\mathrm{O}(n)$
空间复杂度：$\mathrm{O}(logn)$

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left),* right(right) {}* };*/
class Solution {
public:bool isSymmetric(TreeNode* root) {vector<TreeNode*> stack;stack.push_back(root->left);stack.push_back(root->right);while (!stack.empty()) {TreeNode* left = stack.back();stack.pop_back();TreeNode* right = stack.back();stack.pop_back();if (left != nullptr && right != nullptr) {if (left->val == right->val) {stack.push_back(left->left);stack.push_back(right->right);stack.push_back(left->right);stack.push_back(right->left);} else {return false;}} else if (left != nullptr || right != nullptr) {return false;}}return true;}
};