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


  • 0
    L

    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 {
    public:
        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;
                s1.push(t1->right);
                s1.push(t1->left);
                s2.push(t2->left);
                s2.push(t2->right);
            }
            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.