My BFS solution (3ms)


  • 0
    X

    Before I read editorial solution, I didn't realize that we can solve it without using BFS.:(

    class Solution {
    public:
        bool isSymmetric(TreeNode* root) {
            if (!root) return true;
            vector<TreeNode*> left(1), right(1);
            vector<TreeNode*> tmp_left, tmp_right;
            left[0] = right[0] = root;
            while (true) {
                int n = left.size();
                for (int i = 0; i < n; ++i) {
                    if (left[i]->left && !right[i]->right || !left[i]->left && right[i]->right) return false;
                    if (left[i]->right && !right[i]->left || !left[i]->right && right[i]->left) return false;
                    if (left[i]->left) {
                        if (left[i]->left->val != right[i]->right->val) return false;
                        tmp_left.push_back(left[i]->left);
                        tmp_right.push_back(right[i]->right);
                    }
                    if (left[i]->right) {
                        if (left[i]->right->val != right[i]->left->val) return false;
                        tmp_left.push_back(left[i]->right);
                        tmp_right.push_back(right[i]->left);
                    }
                }
                if (tmp_left.empty()) break;
                else {
                    left.swap(tmp_left);
                    right.swap(tmp_right);
                    tmp_left.clear();
                    tmp_right.clear();                
                }
            }
            return true;
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.