跳转至

101. 对称二叉树

力扣链接(简单)：https://leetcode.cn/problems/symmetric-tree

这是一道标注为简单却不简单的题。

给你一个二叉树的根节点 root ， 检查它是否轴对称。

示例 1：

img

Text Only
1
2
输入：root = [1,2,2,3,4,4,3]
输出：true

示例 2：

img

Text Only
1
2
输入：root = [1,2,2,null,3,null,3]
输出：false

提示：

  • 树中节点数目在范围 [1, 1000] 内
  • -100 <= Node.val <= 100

进阶：你可以运用递归和迭代两种方法解决这个问题吗？

个人题解

递归法

C++
 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
/**
 * Definition for a binary tree node.
 * 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) {}
 * };
 */
class Solution {
public:
    // 对称二叉树其实是比较左右子树是否相等
    // 首先写一个比较函数
    bool compare(TreeNode* left, TreeNode* right) {
        // 先处理节点为空的情况
        if(left == NULL && right == NULL) return true;
        else if(left != NULL && right == NULL) return false;
        else if(left == NULL && right != NULL) return false;
        else if(left->val != right->val) return false;

        // 处理节点不为空且相等的情况，递归判断
        // 递归判断子树，内侧和外侧
        bool outside = compare(left->left, right->right);
        bool inside = compare(left->right, right->left);

        return outside && inside;
    }

    bool isSymmetric(TreeNode* root) {
        if(!root) return true;
        return compare(root->left, root->right);
    }
};

迭代法

C++
 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
/**
 * Definition for a binary tree node.
 * 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) {}
 * };
 */
class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        // 对称二叉树其实是比较左右子树是否相等
        // 用栈也是一样的，只需要注意一下取出元素的顺序而已
        queue<TreeNode*> que;
        if(root == NULL) return true;

        que.push(root->left);
        que.push(root->right);

        while(!que.empty()) {
            // 取出队列中的「节点对」进行比较
            auto leftNode = que.front(); que.pop();
            auto rightNode = que.front(); que.pop();

            // 注意这里是continue不是return true
            // 这里均为空只能代表当前「节点对」是为空且相等的
            // 此时应该跳过对其子节点的push操作，故continue
            if(!leftNode && !rightNode) continue;

            // 处理不相等的情况
            if(!leftNode || !rightNode) return false;
            else if(leftNode->val != rightNode->val) return false;

            // 当前层比较通过，进行下一层比较
            // 此处逻辑和递归法是一致的
            que.push(leftNode->left);
            que.push(rightNode->right);

            que.push(leftNode->right);
            que.push(rightNode->left);
        }
        return true;
    }
};