101. Symmetric Tree

2020, Nov 16 2 mins read

1. Description

Given the root of a binary tree, check whether it is a mirror of itself (i.e., symmetric around its center).

2. Example

Example 1

Example 1
Input: root = [1,2,2,3,4,4,3]
Output: true

Example 2

Example 2
Input: root = [1,2,2,null,3,null,3]
Output: false

3. Constraints

The number of nodes in the tree is in the range [1, 1000].
-100 <= Node.val <= 100

4. Solutions

Depth-first Search

n is the number of nodes in root
Time complexity: O(n)
Space complexity: O(logn->n)

class Solution {
public:
    bool isSymmetric(TreeNode *root) {
        return is_symmetric(root->left, root->right);
    }

private:
    bool is_symmetric(TreeNode *root1, TreeNode *root2) {
        if (root1 == nullptr && root2 == nullptr) {
            return true;
        }
        if (root1 == nullptr && root2 == nullptr) {
            return false;
        }

        return root1->val == root2->val && is_symmetric(root1->left, root2->right) &&
            is_symmetric(root1->right, root2->left);
    }
};

Breadth-first Search

n is the number of nodes in root
Time complexity: O(n)
Space complexity: O(logn->n)

class Solution {
public:
    bool isSymmetric(TreeNode *root) {
        queue<TreeNode *> left_first_nodes{{root}}, right_first_nodes{{root}};
        while (!left_first_nodes.empty() && !right_first_nodes.empty()) {
            const int m = left_first_nodes.size(), n = right_first_nodes.size();
            for (int i = 0; i < m; ++i) {
                auto left_node = left_first_nodes.front();
                left_first_nodes.pop();

                auto right_node = right_first_nodes.front();
                right_first_nodes.pop();

                if ((left_node == nullptr) != (right_node == nullptr)) {
                    return false;
                }

                if (left_node != nullptr && right_node != nullptr) {
                    if (left_node->val != right_node->val) {
                        return false;
                    }

                    left_first_nodes.push(left_node->left);
                    left_first_nodes.push(left_node->right);

                    right_first_nodes.push(right_node->right);
                    right_first_nodes.push(right_node->left);
                }
            }
        }

        return true;
    }
};