C++ recursive & non-recursive solutions


  • 0
    • Recursive
    class Solution {
    private:
        bool dfs(TreeNode* p, TreeNode* q) {
            if (p) {
                if (!q) return false;
                return p->val == q->val && dfs(p->left, q->right) && dfs(p->right, q->left);
            } 
            return !q;
        }
    public:
        bool isSymmetric(TreeNode* root) {
            if (!root) return true;
            return dfs(root->left, root->right);
        }
    };
    
    • Non-recursive
    class Solution {
    public:
        bool isSymmetric(TreeNode* root) {
            vector<TreeNode*> helper {root}, tmp;
            while (!helper.empty()) {
                for (int i=0, j=helper.size()-1; i < j; i++, j--) {
                    if (helper[i]) {
                        if (!helper[j] || helper[i]->val != helper[j]->val) return false;
                    } else if (helper[j]) return false; 
                }
                tmp.clear();
                for (TreeNode* t : helper) {
                    if (t) {
                        tmp.push_back(t->left);
                        tmp.push_back(t->right);
                    }
                }
                tmp.swap(helper);
            }
            return true;
        }
    };
    

Log in to reply
 

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