HHot 100C++ 图解

101. 对称二叉树

简单 二叉树 3 帧动画 在力扣上做

一句话套路递归比较(左左,右右)与(左右,右左)

题目描述

给你一个二叉树的根节点 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 右.左 同时成立。

所以必须写一个接收「两个结点」的递归函数 —— 这是镜像题的通用范式。

图解

3 2 4 1 4 2 3
二叉树(来自本仓库测试数据,nullopt 表示空位)

逐帧动画

1 / 3

快捷键:← → 单步,空格播放 / 暂停。

C++17 题解

src/08_binary_tree.cpp15 行
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);      // 内侧配内侧
  }
};
}

单元测试

以下用例都在本仓库里实际编译运行过,图解里的数据也取自这里。

TEST q101_symmetric_tree8 行
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));

↑↓ 选择↵ 打开/ 随时唤起