การกลับด้าน Binary Tree ใน JavaScript

สมมติเรามี binary tree แบบนี้:

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

เราจำเป็นต้องเขียนฟังก์ชัน JavaScript ที่รับ root ของ binary tree นี้และกลับด้าน (invert) มัน

เวอร์ชันที่กลับด้านแล้วจะเป็นแบบนี้:

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

ตัวอย่างโค้ด

// class สำหรับ tree node เดียว
class Node{
  constructor(val){
    this.val = val;
    this.left = null;
    this.right = null;
  };
};
// class สำหรับ binary tree
class BinaryTree{
  constructor(){
    this.root = null;
  };
  insert = (data) => {
    const newNode = new Node(data);
    if(this.root === null){
      this.root = newNode;
    }else{
      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);
      }
    }
  };
  // ฟังก์ชันกลับด้าน 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);
// การ traverse ขวา-ซ้าย ก่อนกลับด้าน
Tree.traverse(Tree.root);
Tree.invert(Tree.root);
console.log('after inversion');
// traversal ขวา-ซ้าย หลังกลับด้าน
Tree.traverse(Tree.root);

ผลลัพธ์

ผลลัพธ์ที่แสดงในคอนโซลจะเป็นดังนี้:

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