A mirror image of a binary tree

1. Topic description

Operates on the given binary tree to transform it into a mirror image of the source binary tree.

Example 2.

3

The recursive approach is to start by iterating through a node and simply swap its two children,

When you swap all the left and right children of the non-leaf nodes, you get a mirror image of the tree

Non-recursive approach: Use queues, similar to hierarchical traversal

4. A Java implementation

The recursive implementation

/** public class TreeNode { int val = 0; TreeNode left = null; TreeNode right = null; public TreeNode(int val) { this.val = val; }} * /
public class Solution {
    public void Mirror(TreeNode root) {
        if (root == null) {return ;
        }
        if (root.left == null && root.right == null) {return;
        }
        
        TreeNode temp; // Swap left and right subtrees
        temp = root.left;
        root.left = root.right;
        root.right = temp;
        
        Mirror(root.left); // Recursively swap the left subtreeMirror(root.right); }}Copy the code

Non-recursive implementation, using a queue implementation, similar to hierarchical traversal of a tree

/** public class TreeNode { int val = 0; TreeNode left = null; TreeNode right = null; public TreeNode(int val) { this.val = val; }} * /
import java.util.Queue;
import java.util.LinkedList;
 
public class Solution {
    public void Mirror(TreeNode root) {
        if (root == null)
        {
            return;
        }        // Use queues
        Queue<TreeNode> q = new LinkedList();
        q.offer(root);
        
        while(! q.isEmpty()){ TreeNode node = q.poll();// Swap elements
            TreeNode temp;
            if(node.left ! =null|| node.right ! =null){
                temp = node.left;
                node.left = node.right;
                node.right = temp;
            }
            
            if(node.left ! =null){
                q.offer(node.left);
            }
            if(node.right ! =null){ q.offer(node.right); }}}}Copy the code

5. Python implementation

The recursive implementation

# -*- coding:utf-8 -*-
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
    # return the root node of the mirror tree
    def Mirror(self, root) :
        # write code here
        if not root:
            return None 
        if not root.left and not root.right:
            return root 
        root.left, root.right = root.right, root.left 
        self.Mirror(root.left)
        self.Mirror(root.right)
Copy the code

Non-recursive implementation, queue

# -*- coding:utf-8 -*-
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
    # return the root node of the mirror tree
    def Mirror(self, root) :
        # write code here
        if not root:
            return None 
        nodeQue = [root]
        while len(nodeQue) > 0:
            nodeNum, count = len(nodeQue), 0
            while nodeNum > count:
                count += 1
                node = nodeQue.pop(0)
                node.left, node.right = node.right, node.left 
                if node.left:
                    nodeQue.append(node.left)
                if node.right:
                    nodeQue.append(node.right)
Copy the code

If you found this article useful, please click “Watching”