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
进阶:你可以运用递归和迭代两种方法解决这个问题吗?
思路
时间
O(n)空间
O(h)思路
对称不是「左右子树结构相同」,而是「互为镜像」:左.左 vs 右.右 与 左.右 vs 右.左 同时成立。
所以必须写一个接收「两个结点」的递归函数 —— 这是镜像题的通用范式。
图解
二叉树(来自本仓库测试数据,
nullopt 表示空位)逐帧动画
1 / 3
快捷键:← → 单步,空格播放 / 暂停。
C++17 题解
namespace lc0101 {
class Solution {
public:
bool isSymmetric(TreeNode* root) { return !root || mirror(root->left, root->right); }
private:
static bool mirror(const TreeNode* a, const TreeNode* b) {
if (!a && !b) return true;
if (!a || !b) return false; // 一边空一边不空
return a->val == b->val && // 自身值
mirror(a->left, b->right) && // 外侧配外侧
mirror(a->right, b->left); // 内侧配内侧
}
};
}
单元测试
以下用例都在本仓库里实际编译运行过,图解里的数据也取自这里。
lc0101::Solution s;
TreeNode* a = buildTree({1, 2, 2, 3, 4, 4, 3});
CHECK_TRUE(s.isSymmetric(a));
freeTree(a);
TreeNode* b = buildTree({1, 2, 2, nullopt, 3, nullopt, 4});
CHECK_FALSE(s.isSymmetric(b));
freeTree(b);
CHECK_TRUE(s.isSymmetric(nullptr));