This is the 8th day of my participation in the August Text Challenge.More challenges in August

JZ 27, Mirror image of binary tree

The question:

Given the root of a binary tree, invert the tree, and return its root.

Example 1:

Input: root =,2,7,1,3,6,9 [4] the Output:,7,2,9,6,3,1 [4]

Example 2:

Input: root = [2,1,3] Output: [2,3,1]

Example 3:

Input: root = [] Output: []

Constraints:
  • The number of nodes in the tree is in the range [0, 100].
  • -100 <= Node.val <= 100

Analysis:

We are asked to invert all nodes in the binary tree. Each node is mapped to its mirror position. Think of the origami experience, that’s the flip, that’s the switch between the left and right child nodes, that’s the first core of the problem; If from down to up, obviously is not easy, but it is difficult to find a corresponding position from the perspective of the nodes of the following us, then from the top down processing, we deal only with nodes from the top down, each time of dealing with the exchange to the nodes around the child, in turn, according to the level one turn, can be a complete reversal of the binary tree, his painting a picture on the paper is easier to think clearly.

Problem solving:

Problem number one, recursion

The easiest way to think about it is to start with the root node, find the left and right child nodes, and swap the two nodes.

     /** * recursively inverts the binary tree */
     public static TreeNode invertMirrorTree(TreeNode root) {
         if (Objects.isNull(root)) {
             return null;
         }
         // Swap left and right child nodes
         TreeNode tempNode = root.left;
         root.left = root.right;
         root.right = tempNode;
         invertMirrorTree(root.left);
         invertMirrorTree(root.right);
 ​
         return root;
     }
Copy the code
Solution 2. Double-endian queue

And from what we’ve done recently, the clever use of a two-endian queue seems to simplify a lot of binary tree traversal.

First, the root node is pushed to the double-endian queue, then the head node is consumed, the left and right child nodes of the head node are swapped, and the left and right child nodes are pushed to the double-endian queue, and so on.

     /** * recursively inverts the binary tree */
     public static TreeNode invertMirrorTreeWithQueue(TreeNode root) {
         if (Objects.isNull(root)) {
             return null;
         }
         LinkedList<TreeNode> treeNodes = newLinkedList<TreeNode>() { { add(root); }};while(! treeNodes.isEmpty()) { TreeNode treeNode = treeNodes.removeFirst();if(treeNode.right ! =null) {
                 treeNodes.add(treeNode.right);
             }
             if(treeNode.left ! =null) {
                 treeNodes.add(treeNode.left);
             }
             // Swap left and right child nodes
             TreeNode temp = treeNode.left;
             treeNode.left = treeNode.right;
             treeNode.right = temp;
         }
 ​
         return root;
     }
Copy the code