[leetcode]: 101. Symmetric Tree

Dear 丶 2022-06-15 04:42 140阅读 0赞

# 1.题目 #

Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).

For example, this binary tree \[1,2,2,3,4,4,3\] is symmetric:

1
       / \
      2   2
     / \ / \
    3  4 4  3

But the following \[1,2,2,null,3,null,3\] is not:

1
    / \
    2   2
     \   \
     3    3

给一棵二叉树，判断这棵树是否镜像对称。

# 2.分析 #

广度优先遍历。  
左子树和右子树遍历的方向相反即可。  
递归or迭代

# 3.代码 #

递归

class Solution {
    public:
        bool judgeSysmetric(TreeNode* left, TreeNode*right) {
            if (left == NULL || right == NULL)
                return left == right;
            if (left->val!=right->val)
                return false;
            return judgeSysmetric(left->left, right->right) && judgeSysmetric(left->right, right->left);
        }
        bool isSymmetric(TreeNode* root) {
            if (root == NULL)
                return true;
            return judgeSysmetric(root->left, root->right);
        }
    };

迭代

bool isSymmetric(TreeNode* root) {
        if (root == NULL)
            return true;
        //左右子树分别用queue存储
        queue<TreeNode*> left;
        left.push(root->left);
        queue<TreeNode*> right;
        right.push(root->right);
        while (!left.empty() && !right.empty()) {
            TreeNode* l = left.front();
            left.pop();
            TreeNode* r = right.front();
            right.pop();
            if (l == NULL && r == NULL)
                continue;
            if (l == NULL || r == NULL)
                return false;
            if (l->val != r->val)
                return false;
            //左边与右边遍历的方向相反。左边从左到右。右边从右到左。
            left.push(l->left);
            left.push(l->right);
            right.push(r->right);
            right.push(r->left);
        }
        return true;
    }