lc.101 镜像对称二叉树

镜像对称：

![[Pasted image 20241124183213.png]]

该问题可以转化为：两个树在什么情况下互为镜像？

如果同时满足下面的条件，两个树互为镜像：

1. 它们的两个根结点具有相同的值；
2. 每个树的右子树都与另一个树的左子树镜像对称；

---

解法

1）递归法

我们可以实现这样一个 递归 函数，通过 同步移动 两个指针的方法来遍历这棵树，p 指针和 q 指针一开始都指向这棵树的根，随后 p 右移时，q 左移，p 左移时，q 右移。每次检查当前 p 和 q 节点的值是否相等，如果相等再判断左右子树是否对称。

    bool check(TreeNode *p, TreeNode *q) {

        if (!p && !q) return true;//如果p,q同时为空,说明上一个根节点是叶子节点

        if (!p || !q) return false;//如果p,q只有一个为空,说明不对称

        return p->val == q->val && check(p->left, q->right) && check(p->right, q->left);//3个条件都满足才能返回true
        
    }

2）层序遍历法

或者也可以用层序遍历，用i, j相向遍历 用于存储每一层的结点的vec数组 ，若每一层的vec数组都是“关于中间元素对称”的，则说明二叉树是镜像对称的；
但是有一个问题是，很容易忽略null结点二导致错误，我们需要在遇到null结点的时候往vec里push_back一个不常见的值，如1000，起到一个占位作用；