101. 对称二叉树 - 力扣(LeetCode)
一、题目要求
给你一个二叉树的根节点 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
进阶:你可以运用递归和迭代两种方法解决这个问题吗?
二、解法1-递归 O(N)
使用递归,从根开始比较左右两边的节点的val是否相同。
class Solution {bool _isSymmetric(TreeNode* left, TreeNode* right) {if (left == nullptr && right == nullptr) // 走到尾,都为空return true;if (left == nullptr && right != nullptr || // 一边走到尾,另外一般不是空right == nullptr && left != nullptr)return false;if (left->val != right->val) // 对称节点不相同return false;return _isSymmetric(left->left, right->right) &&_isSymmetric(left->right, right->left);}
public:bool isSymmetric(TreeNode* root) {if (!root)return true;return _isSymmetric(root->left, root->right);}
};
三、解法2-迭代 O(N)
迭代需要我们维护一个栈,每次循环查看栈顶的两个节点是否对称,如果对称且不为空,就插入这两个节点的四个子节点;如果为空说明走到尾了,就不插入。
class Solution {
public:bool isSymmetric(TreeNode* root) {if (!root)return true;stack<TreeNode*> s; // 栈s.push(root->left);s.push(root->right);while (!s.empty()) {TreeNode* root1 = s.top();s.pop();TreeNode* root2 = s.top();if (root1 == nullptr && root2 == nullptr) { // 为空不再插入节点s.pop();continue;}if (root1 == nullptr && root2 != nullptr ||root2 == nullptr && root1 != nullptr) // 不对称return false;if (root1->val != root2->val) // 不对称return false;s.pop();s.push(root1->left);s.push(root2->right);s.push(root2->left);s.push(root1->right);}return true;}
};