leetcode101.对称二叉树

Question

给你一个二叉树的根节点 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
进阶：你可以运用递归和迭代两种方法解决这个问题吗？ Related Topics 树深度优先搜索广度优先搜索二叉树 👍 1908 👎 0

Answer

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
//同100，递归出口条件不同
bool isMirror(TreeNode* p, TreeNode* q) {
    if (!p && !q)
        return true;//左右两个结点有都为空，出口
    if (!p || !q)
        return false;//左右两个结点只有一个为空，说明不对称
    if (p->val == q->val) {
        return isMirror(p->left, q->right) && isMirror(p->right, q->left);
    } else {
        return false;
    }
}
//递归
bool isSymmetric1(TreeNode* root) {
    if (!root)
        return true;
    return isMirror(root->left, root->right);
}


//迭代
bool isSymmetric2(TreeNode* root) {
    if (!root)
        return true;
    queue<TreeNode*> q;
    q.push(root->left);
    q.push(root->right);
    //左右子树分别比较
    while (!q.empty()) {
        auto p1 = q.front();
        q.pop();
        auto p2 = q.front();
        q.pop();
        if (!p1 && !p2)
            continue;
        if (!p1 || !p2)
            return false;
        if (p1->val != p2->val) {
            return false;
        }
        q.push(p1->left);
        q.push(p2->right);
        q.push(p1->right);
        q.push(p2->left);//注意顺序
    }
    return true;
}

Question

Answer

Attention