C++ recursive and iterarive solutions (3ms and 6ms)

  • 0

    For recursive solution, we compare the symmetric node in each recursion.

    For iterative solution, we pre-orderly traverse the tree and "symmetric pre-orderly" traverse the tree using stack, and compare the node in the processing.

    class Solution {
        bool judge(TreeNode* r1, TreeNode* r2) {
            if (r1 == nullptr || r2 == nullptr) return r1 == r2;
            else if (r1->val != r2->val) return false;
            return judge(r1->left, r2->right) && judge(r1->right, r2->left);
        bool isSymmetric(TreeNode* root) {
            if (root == nullptr) return true;
            //return judge(root->left, root->right);
            stack<TreeNode*> s1; s1.push(root->left);
            stack<TreeNode*> s2; s2.push(root->right);
            while (!s1.empty() && !s2.empty()) {
                TreeNode* t1 = s1.top(); s1.pop();
                TreeNode* t2 = s2.top(); s2.pop();
                if (t1 == nullptr || t2 == nullptr) {
                    if (t1 == t2) continue;
                    else return false;
                if (t1->val != t2->val) return false;
            return s1.empty() && s2.empty();

Log in to reply

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