反转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 BinaryTree{
   constructor(){
      //二叉树的根
      this.root = null;
   };
   insert = (data) => {
      //用数据创建一个新节点
      const newNode = new Node(data);
      //如果root为null，则此节点将为root-
      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);
         }
      }
   };
   //反转二叉树的功能
   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);
//原始的从右到左遍历
Tree.traverse(Tree.root);
Tree.invert(Tree.root);
console.log('after inversion');
//反转后从右向左遍历
Tree.traverse(Tree.root);

输出结果

控制台中的输出将是-

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