“Sword means Offer” 5. Mirror image and printing of binary tree

Introduction to Binary Tree

Basic structure:

function TreeNode(x) {
 this.val = x;
 this.left = null;
 this.right = null;
 }

Definition of traversal of binary tree’s pre-order, mid-order and post-order;

Preorder traversal: for any subtree, first access heel, then traverse its left subtree, and finally traverse its right subtree;

Mid-order traversal: for any subtree, first traverse its left subtree, then access its root, and finally traverse its right subtree;

Postorder traversal: For any subtree, first traverse its left subtree, then traverse its right subtree, and finally access the root.

Topic 1 Mirror Image of Binary Tree

1.1 topic description

Operate a given binary tree and transform it into a mirror image of the source binary tree.

Enter a description:
Mirror Definition of Binary Tree: Source Binary Tree
8
/  \
6   10
/ \  / \
5  7 9 11
Mirror binary tree
8
/  \
10   6
/ \  / \
11 9 7  5

1.2 problem-solving ideas

Recursively swap the positions of two word trees of binary tree.

1.3 code

function Mirror(root)
 {
 if(root){
 const temp = root.right;
 root.right = root.left;
 root.left = temp;
 Mirror(root.right);
 Mirror(root.left);
 }
 }

Topic 2 Printing Binary Tree from Top to Bottom

2.1 topic description

Each node of the binary tree is printed from top to bottom, and nodes of the same layer are printed from left to right.

2.2 Ideas for Solving Problems

1. With the help of queue FIFO data structure

2. Let each layer of binary tree enter the queue in turn

3. Print the values in the queue in turn

2.3 code

function PrintFromTopToBottom(root) {
 const queue = [];
 const print = [];
 if(root !  = null){
 queue.push(root);
 }
 while (queue.length > 0) {
 const current = queue.shift();
 print.push(current.val);
 if (current.left) {
 queue.push(current.left);
 }
 if (current.right) {
 queue.push(current.right);
 }
 }
 return print;
 }