LeetCode 算法：对称二叉树 c++

原题链接🔗：对称二叉树
难度：简单⭐️

题目

给你一个二叉树的根节点 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. 解题思路：

解决LeetCode上"对称二叉树"问题的解题思路主要依赖于递归和树的遍历。以下是详细的解题步骤和思路：

1. 理解问题：首先要理解什么是对称二叉树。如果一棵二叉树的左子树与右子树以根节点为中心镜像对称，那么这棵二叉树就是对称的。

2. 定义递归函数：定义一个递归函数，用于比较两个节点的子树是否对称。这个函数将接收两个参数，分别代表树的两个子节点。

3. 递归终止条件：

   • 如果两个节点都为空，返回true，因为两个空节点是对称的。
   • 如果只有一个节点为空，或者两个节点的值不相等，返回false。

4. 递归逻辑：

   • 对于非空节点，比较它们的值是否相等。如果不相等，直接返回false。
   • 如果值相等，递归地调用函数，比较左子树的右子节点和右子树的左子节点是否对称。

5. 编写递归函数：实现递归函数，使用条件语句来处理递归终止条件，并使用递归调用来比较子树。

6. 主函数：实现一个主函数，用于接收二叉树的根节点，并调用递归函数，传入根节点的左右子节点作为参数。

7. 测试：编写测试用例来验证算法的正确性，包括对称的二叉树和非对称的二叉树。

8. 优化：考虑算法的时间复杂度和空间复杂度。对于树的每个节点，我们只进行一次比较，所以时间复杂度是O(n)，其中n是树中的节点数。空间复杂度取决于递归调用的深度，最坏情况下是O(h)，其中h是树的高度。

9. 边界条件：确保处理了所有边界条件，如空树或只有一个节点的树。

2. 复杂度：

• 时间复杂度：这里遍历了这棵树，渐进时间复杂度为 O(n)。
• 空间复杂度：这里的空间复杂度和递归使用的栈空间有关，这里递归层数不超过 n，故渐进空间复杂度为 O(n)。

3. c++ demo：

#include <iostream>struct TreeNode {int val;TreeNode* left;TreeNode* right;TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};class Solution {
public:bool isSymmetric(TreeNode* root) {if (!root) return true;  // 如果根节点为空，树是对称的return isMirror(root->left, root->right);}private:bool isMirror(TreeNode* left, TreeNode* right) {if (!left && !right) return true;  // 两个子节点都为空，是镜像的if (left && !right || !left && right) return false;  // 一个为空，另一个不为空，不是镜像的if (left->val != right->val) return false;  // 节点值不相等，不是镜像的// 递归地检查左子树的右子节点和右子树的左子节点return isMirror(left->right, right->left) && isMirror(left->left, right->right);}
};int main() {Solution solution;// 创建一个对称的二叉树//       1//      / \//     2   2//    / \ / \//   3  4 4  3TreeNode* root = new TreeNode(1);root->left = new TreeNode(2);root->right = new TreeNode(2);root->left->left = new TreeNode(3);root->left->right = new TreeNode(4);root->right->left = new TreeNode(4);root->right->right = new TreeNode(3);// 测试对称二叉树bool result = solution.isSymmetric(root);std::cout << "The binary tree is " << (result ? "symmetric" : "not symmetric") << "." << std::endl;// 清理分配的内存delete root->left->left;delete root->left->right;delete root->left;delete root->right->left;delete root->right->right;delete root;return 0;
}

• 输出结果：

The binary tree is symmetric.