การแปลงไบนารีทรีใน JavaScript

สมมติว่าเรามีไบนารีทรีแสดงแบบนี้ -

      4
   /    \
  2      7
 / \    / \
1 3     6  9

เราจำเป็นต้องเขียนฟังก์ชัน JavaScript ที่รับรูทของไบนารีทรีนี้และกลับด้าน

ไบนารีทรีด้านบนนี้จะมีลักษณะเช่นนี้ -

      4
      / \
    7    2
   / \ / \
   9 6 3 1

ตัวอย่าง

รหัสสำหรับสิ่งนี้จะเป็น −

// class for a single tree node
class Node{
   constructor(val){
      this.val = val;
      this.left = null;
      this.right = null;
   };
};
// class for binary tree
class BinaryTree{
   constructor(){
      // root of the binary tree
      this.root = null;
   };
   insert = (data) => {
      // creating a new node with data
      const newNode = new Node(data);
      // if root is null, then this node will be the root
      if(this.root === null){
         this.root = newNode;
      }else{
         // otherwise we find the correct position to insert this node
         this.insertData(this.root, newNode);
      };
   };
   insertData = (node, newNode) => {
      if(newNode.val < node.val){
         if(node.left === null){
            node.left = newNode;
         }else{
            this.insertData(node.left, newNode);
         }
      }else{
         if(node.right === null){
            node.right = newNode;
         }else{
            this.insertData(node.right, newNode);
         }
      }
   };
   // function to invert the binary tree
   invert = (node) => {
      if(node === null){
         return;
      };
      [node.left, node.right] = [node.right, node.left];
      this.invert(node.right);
      this.invert(node.left);
   }
   traverse = (node) => {
      if(node === null){
         return;
      };
      this.traverse(node.right);
      console.log(node.val);
      this.traverse(node.left);
   };
};
const Tree = new BinaryTree();
Tree.insert(2);
Tree.insert(7);
Tree.insert(4);
Tree.insert(1);
Tree.insert(9);
Tree.insert(3);
Tree.insert(6);
// original right to left traversal
Tree.traverse(Tree.root);
Tree.invert(Tree.root);
console.log('after inversion');
// traversal right to left after inversion
Tree.traverse(Tree.root);

ผลลัพธ์

และผลลัพธ์ในคอนโซลจะเป็น −

9
7
6
4
3
2
1
after inversion
1
2
3
4
6
7
9