Mirror of Binary Tree with / without recursion!


  • 1
    J

    /****************************************
    // SOLUTION:1 WITH recursion
    ****************************************/

    void swapNodeElement((Node *nodePtr);

    void mirror(Node *nodePtr)
    {

    if(nodePtr == NULL) return;
    
    //swap left and right element of nodePtr
    swapNodeElement(nodePtr);
    
    //Call mirror function to swap element of left and right node
    mirror(nodePtr->left);
    mirror(nodePtr->right);
    

    }

    void swapNodeElement((Node *nodePtr)
    {

    Node *temp = nodePtr->left;
    nodePtr->left = nodePtr->right;
    nodePtr->right = temp;
    

    }

    /****************************************
    // SOLUTION:2 WITHout recursion
    ****************************************/

    // Using STL library to push Node in queue.

    // Pop the Node from queue and swap left / right node.

    // Push left/right node in Queue

    void swapNodeElement((Node *nodePtr);

    void mirror(Node *nodePtr)
    {

    if(nodePtr == NULL) return;
    if(nodePtr->left == NULL && nodePtr->right == NULL) return;
    std::queue<Node *> queuePtr;
    queuePtr.push(nodePtr);
    
    do
    {
            nodePtr = queuePtr.front();
            queuePtr.pop();
    
            swapNodeElement(nodePtr);
    
            if(nodePtr->left != NULL) queuePtr.push(nodePtr->left);
            if(nodePtr->right != NULL) queuePtr.push(nodePtr->right);
    }while( !queuePtr.empty());
    

    }


  • 0
    J

    Both recursieve & non-recursive version in C#

           public static void MirrorRecursive(BTreeNode root)
            {
                if (root == null)
                    return;
    
                var leftNode = root.Left;
                var rightNode = root.Right;
                root.Left = rightNode;
                root.Right = leftNode;
    
                if(root.Right != null)
                    MirrorRecursive(root.Right);
                if(root.Left != null)
                    MirrorRecursive(root.Left);
    
            }
    
            public static void MirrorLoo(BTreeNode root)
            {
                Queue<BTreeNode> nodes = new Queue<BTreeNode>();
                int level = 0;
                int currentLevelTotal = 0;
                int levelCounter = 0;
                nodes.Enqueue(root);
                while (nodes.Count > 0)
                {
                    //current level
                    level++;
                    //count of each level
                    currentLevelTotal = nodes.Count;
                    levelCounter = 0;
                    while (levelCounter < currentLevelTotal)
                    {
                        levelCounter++;
                        //switch
                        var node = nodes.Dequeue();
                        var temp = node.Left;
                        node.Left = node.Right;
                        node.Right = temp;
    
                        if (node.Left != null)
                            nodes.Enqueue(node.Left);
                        if (node.Right != null)
                            nodes.Enqueue(node.Right);
                    }
                }
            }
    

  • 0
    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    public class Solution {
        
        public TreeNode invertTreeRecursive(TreeNode root) {
             if(null == root) {
                 return null;
             }
    
             TreeNode revert_left = invertTreeRecursive(root.left);
             TreeNode revert_right = invertTreeRecursive(root.right);
             
             root.right = revert_left;
             root.left = revert_right;
             
             return root;
        }
    
        public TreeNode invertTreeIterative(TreeNode root) {
            if(null == root) {
                return null;
            }
            
            Deque<TreeNode> q = new ArrayDeque<>();
            q.add(root);
            
            while(!q.isEmpty()) {
                int size = q.size();
                
                while(size > 0) {
                    TreeNode top = q.poll();
                    
                    TreeNode right = top.right;
                    
                    if(null != top.left) {
                        q.add(top.left);
                    }
                    
                    if(null != top.right) {
                        q.add(top.right);
                    }
                    
                    top.right = top.left;
                    top.left = right;
                    
                    --size;
                }
            }
            
            return root;
        }
    }
    
    

Log in to reply
 

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