Recursive and iterative (DFS and BFS) in C++. Easy to understand.


  • 12
    B

    Iterative in BFS:

    bool isSymmetric(TreeNode* root) {
        if(!root) return true;
        queue<nodepair> q;
        q.push(make_pair(root->left, root->right));
        while(!q.empty()){
            nodepair p = q.front();
            q.pop();
            if(!p.first && !p.second) continue;
            if(!p.first || !p.second) return false;
            if(p.first->val != p.second->val) return false;
            q.push(make_pair(p.first->left, p.second->right));
            q.push(make_pair(p.first->right, p.second->left));
        }
        return true;
    }
    

    Iterative in DFS:

    bool isSymmetric(TreeNode* root) {
        if(!root) return true;
        stack<TreeNode*> sl, sr;
        sl.push(root);
        sr.push(root);
        TreeNode * lp = root->left, *rp = root->right;
        while(lp || ! sl.empty() || rp || !sl.empty()){
            if((!lp && rp) || (lp && !rp)) return false;
            if(lp && rp){
                if(lp->val != rp->val) return false;
                sl.push(lp);
                sr.push(rp);
                lp = lp->left;
                rp = rp->right;
            }else{
                lp = sl.top()->right;
                rp = sr.top()->left;
                sl.pop();
                sr.pop();
            }
        }
        return true;
    }
    

    Recursive:

    bool isSymmetric(TreeNode* root) {
        if(!root) return true;
        return helper(root->left, root->right);
    }
    bool helper(TreeNode* left, TreeNode* right){
        if(!left && !right) return true;
        if(!left || !right) return false;
        return (left->val == right->val) && helper(left->left, right->right) && helper(left->right, right->left);
    }

  • 1
    Y

    Thanks for sharing! I rewrote your code in Java :)

    Iterative BFS:

    private class Pair {
        TreeNode left;
        TreeNode right;
        
        Pair(TreeNode left, TreeNode right) {
            this.left = left;
            this.right = right;
        }
    }
    
    public boolean isSymmetric(TreeNode root) {
        if (root == null) {
            return true;
        }
        Queue<Pair> queue = new LinkedList<>();
        queue.offer(new Pair(root.left, root.right));
        while (!queue.isEmpty()) {
            Pair current = queue.poll();
            TreeNode left = current.left;
            TreeNode right = current.right;
            if (left == null && right == null) {
                continue;
            }
            if (left == null || right == null) {
                return false;
            }
            if (left.val != right.val) {
                return false;
            }
            queue.offer(new Pair(left.left, right.right));
            queue.offer(new Pair(left.right, right.left));
        }
        return true;
    }
    

    Iterative DFS:

    public boolean isSymmetric(TreeNode root) {
        if (root == null) {
            return true;
        }
        Stack<TreeNode> leftStack = new Stack<>();
        Stack<TreeNode> rightStack = new Stack<>();
        TreeNode left = root.left;
        TreeNode right = root.right;
        while (left != null || right != null || !leftStack.isEmpty() || !leftStack.isEmpty()) {
            if (left == null && right != null) {
                return false;
            }
            if (left != null && right == null) {
                return false;
            }
            if (left != null && right != null) {
                if (left.val != right.val) {
                    return false;
                }
                leftStack.push(left);
                rightStack.push(right);
                left = left.left;
                right = right.right;
            } else {
                left = leftStack.pop().right;
                right = rightStack.pop().left;
            }
        }
        return true;
    }
    

    Recursive:

    public boolean isSymmetric(TreeNode root) {
        if (root == null) {
            return true;
        }
        return isSymmetric(root.left, root.right);
    }
    
    private boolean isSymmetric(TreeNode root1, TreeNode root2) {
        if (root1 == null || root2 == null) {
            return root1 == null && root2 == null;
        }
        if (root1.val != root2.val) {
            return false;
        }
        return isSymmetric(root1.left, root2.right) && isSymmetric(root1.right, root2.left);
    }

  • 0
    H
    This post is deleted!

  • 0
    J

    @Yanning said in Recursive and iterative (DFS and BFS) in C++. Easy to understand.:

    private class Pair {
    TreeNode left;
    TreeNode right;

    Pair(TreeNode left, TreeNode right) {
        this.left = left;
        this.right = right;
    }
    

    }

    If we directly run your code on leetcode, it gives an error that nodepair does not exist. I have been running into this problem a lot of times doing c++ here in leetcode, make_pair() function does not work. Is there any thing I should define up on top before using the make_pair() functions?


  • 0
    J
    bool isSymmetric(TreeNode* root) {        
            if(!root) return true;
            queue<TreeNode*> q;
            TreeNode* tmp;
            tmp->left=root->left;
            tmp->right=root->right;
            q.push(tmp);
            
        while(!q.empty()){
            TreeNode* p = q.front();
            q.pop();
            if(p->left!=NULL && p->right!=NULL) continue;
            if(p->left!=NULL || p->right!=NULL) return false;
            if(p->left->val != p->right->val) return false;
            TreeNode* tmp1;
            tmp1->left=p->left->left;
            tmp1->right=p->right->right;
            q.push(tmp1);
            TreeNode* tmp2;
            tmp2->left=p->left->right;
            tmp2->right=p->right->left;
            q.push(tmp2);
        }
        return true;
        }
    

    Even if I changed the code to this way, it still gives me compile error. So what should be the right way of applying the idea in C++?


Log in to reply
 

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