阅读量:4
leetcode101. 对称二叉树
给你一个二叉树的根节点 root ， 检查它是否轴对称。
示例 1：
输入：root = [1,2,2,3,4,4,3]
输出：true
示例 2：
输入：root = [1,2,2,null,3,null,3]
输出：false
递归法
1.定义辅助函数 check：这个函数接收两个参数，分别是指向二叉树节点的指针 p 和 q。它的作用是递归地检查从 p 和 q 出发的子树是否镜像对称。
2.处理空节点情况：在 check 函数中，首先检查 p 和 q 是否都为空。如果都为空，则说明这两个子树是对称的，返回 true。如果其中一个为空而另一个不为空，则说明这两个子树不对称，返回 false。
3.比较节点值：如果 p 和 q 都不为空，接下来比较它们的值。如果值不相等，则说明这两个子树不对称，返回 false。
4.递归检查子树：如果 p 和 q 的值相等，算法会继续递归地检查 p 的左子树和 q 的右子树是否对称，以及 p 的右子树和 q 的左子树是否对称。这一步骤是关键，因为它确保了对称性的检查是全面的。只有当这两个递归调用都返回 true 时，check 函数才会返回 true。
5.实现主函数 isSymmetric：这个函数是对外的接口，它接收一个参数 root，即二叉树的根节点。isSymmetric 函数通过调用 check 函数并传入 root 和 root 作为参数来实现对整个二叉树的对称性检查。这意味着算法会从根节点出发，检查其左右子树是否镜像对称。
递归法具体代码如下：
class Solution { public: bool check(TreeNode *p, TreeNode *q) { if (!p && !q) return true; if (!p || !q) return false; return p->val == q->val && check(p->left, q->right) && check(p->right, q->left); } bool isSymmetric(TreeNode* root) { return check(root, root); } }; 迭代法
递归代码变成迭代，往往需要辅助队列或者辅助栈，我们这里使用辅助队列。
初始节点入队列：首先把root节点两次入辅助队列。
层序遍历：使用一个 while 循环进行层序遍历，直到队列为空。在每次循环中，从队列中取出两个节点 u 和 v。
处理空节点：如果 u 和 v 都为空，说明当前层的两个节点是对称的，继续处理下一层。如果其中一个为空而另一个不为空，或者它们的值不相等，说明这两个子树不对称，函数返回 false。
对称性检查：如果 u 和 v 的值相等，算法会将 u 的左子节点和 v 的右子节点，以及 u 的右子节点和 v 的左子节点入队。这样，下一次循环时，它们会被取出并进行比较，确保左子节点与右子节点的值相等，从而保证对称性。
迭代法完整代码如下：
class Solution { public: bool check(TreeNode *u, TreeNode *v) { queue <TreeNode*> q; q.push(u); q.push(v); while (!q.empty()) { u = q.front(); q.pop(); v = q.front(); q.pop(); if (!u && !v) continue; if ((!u || !v) || (u->val != v->val)) return false; q.push(u->left); q.push(v->right); q.push(u->right); q.push(v->left); } return true; } bool isSymmetric(TreeNode* root) { return check(root, root); } }; 