c++中如何判断二叉树是否对称_c++二叉树对称判断方法

判断二叉树是否对称需验证左右子树是否镜像。递归法通过比较根值及子树对称性实现，代码简洁但深树可能栈溢出；迭代法用队列层序对比节点，空间稳定适合深树。两者时间复杂度均为O(n)，空间复杂度为O(h)。

判断二叉树是否对称，本质上是判断二叉树的左右子树是否互为镜像。可以通过递归或迭代的方式实现。

递归方法判断二叉树对称

核心思路：定义一个辅助函数，比较左子树和右子树是否镜像对称。

两个子树镜像的条件是：

• 它们的根节点值相等；
• 左子树的左子树与右子树的右子树对称；
• 左子树的右子树与右子树的左子树对称。

// 二叉树节点定义 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) {} };

// 递归辅助函数 bool isMirror(TreeNode left, TreeNode right) { if (!left && !right) return true; if (!left || !right) return false; return (left->val == right->val) && isMirror(left->left, right->right) && isMirror(left->right, right->left); }

// 判断二叉树是否对称 bool isSymmetric(TreeNode* root) { if (!root) return true; return isMirror(root->left, root->right); }

迭代方法判断二叉树对称

使用队列模拟层序遍历，每次取出两个节点进行比较，顺序为：左子树的左孩子与右子树的右孩子，左子树的右孩子与右子树的左孩子。

立即学习“C++免费学习笔记（深入）”；

#include <queue> using namespace std;

bool isSymmetric(TreeNode* root) { if (!root) return true;

queue<TreeNode*> q;
q.push(root->left);
q.push(root->right);

while (!q.empty()) {
    TreeNode* node1 = q.front(); q.pop();
    TreeNode* node2 = q.front(); q.pop();

    if (!node1 && !node2) continue;
    if (!node1 || !node2) return false;
    if (node1->val != node2->val) return false;

    q.push(node1->left);
    q.push(node2->right);
    q.push(node1->right);
    q.push(node2->left);
}

return true;

}

NameGPT名称生成器

免费AI公司名称生成器，AI在线生成企业名称，注册公司名称起名大全。

0

查看详情

使用说明与注意事项

递归方法代码简洁、逻辑清晰，适合理解对称结构的本质。但深度过大时可能引发栈溢出。

迭代方法空间效率更稳定，适合处理深度较大的树，但需要手动管理队列。

两种方法时间复杂度均为 O(n)，n 为节点数；空间复杂度平均为 O(h)，h 为树的高度。

基本上就这些。根据实际场景选择递归或迭代方式即可。

以上就是c++++中如何判断二叉树是否对称_c++二叉树对称判断方法的详细内容，更多请关注php中文网其它相关文章！