在 JavaScript 中反转二叉树
问题陈述要求用户给定一个二叉树，您需要找到二叉树元素的镜像，以便反转树枝的相应和平行兄弟。简而言之，给定原始二叉树作为输入，反转整个二叉树。
问题陈述的输出看起来像输入二叉树的反向函数，作为要实现的摘要。
什么是 JavaScript 中的树
树是指用于保存数据的优化数据结构之一，其中树中存在的数据点称为树的节点。树数据结构自动可视化为现实世界中的树。树的顶部数据点称为根节点，从树中伸出的分支就像现实世界中的树一样称为子节点，这些分支也可以有递归分支，这些分支有子节点或没有子节点。
树数据结构对从单个节点伸出的分支(称为子节点)没有限制，但数据结构树本身存在许多类型的树。
什么是 JavaScript 中的二叉树
二叉树是 JavaScript 中的一种树，其中树的每个分支最多只包含两个子节点。它也按时间顺序排列，其中树的左侧值小于根节点，而树的右侧值大于根节点，使树完全平衡。
什么是 JavaScript 中的倒置二叉树
倒置二叉树是指采用特定规则对树进行倒置，其中二叉树的左子节点变为二叉树的右子节点。此特定条件适用于树的递归子分支。
算法 - 创建节点
在二叉搜索树中创建节点的算法如下 -
步骤 1:声明一个名为 Node 的类，该类接受一个带有值参数的构造函数，即其中的实际数据点。
步骤 2:构造函数将使用 JavaScript 中的 this 将实际数据点初始化为当前上下文和引用，同时将左指针和右指针初始化为 null，以便可以在树中插入数据点的左指针和右指针。算法的 cCode -
算法的代码 - 创建节点
class Node {
constructor(value){
this.value = value;
this.left = null;
this.right = null;
}
}
算法 - 打印树
使用 createNode 函数创建节点后向用户显示节点的算法，它返回给定节点中存在的所有值。
步骤 1:声明一个函数 printTree，该函数以用户提供的根值作为核心输入的参数。
步骤 2:声明一个树元素列表和队列，使用空数组初始化列表，并使用根作为参数传递给函数的队列。
步骤 3:直到队列的长度不小于 0，我们需要将第一个元素移到第 0 个索引处，然后使用 javascript 中的 push 方法将其推回到元素列表中。
步骤 4:这是算法的递归步骤，检查树的左子分支是否不为空，然后将左子分支元素推入列表中。
步骤 5:这是算法的递归步骤，检查树的右子分支是否不为空，然后将右子分支元素推入列表中。
算法代码 - 打印树
const printTree = (root) => {
let listOfTreeElements = [];
let queueOfTreeElements = [root];
while (queueOfTreeElements.length) {
let currentNode = queueOfTreeElements.shift();
listOfTreeElements.push(currentNode.value);
if(currentNode.left) queueOfTreeElements.push(currentNode.left);
if(currentNode.right) queueOfTreeElements.push(currentNode.right);
}
return listOfTreeElements;
}
现在是时候调用函数来执行一些特定的任务，即创建节点并使用 printTree 算法以二叉树的形式显示节点。
新对象将从声明为 Node 的类中创建，并将值插入到左、右子分支中。
示例
let originalTree = new Node(4); originalTree.left = new Node(2); originalTree.right = new Node(7); originalTree.left.left = new Node(1); originalTree.left.right = new Node(3); originalTree.right.left = new Node(9); originalTree.right.right = new Node(0); console.log(printTree(originalTree));
The output of the binary search tree looks like after insertion of data points is :
输出
Binary Search Tree after insertion : [ 4, 2, 7, 1, 3, 9, 0 ]
算法 - findInvertedBinaryTree 方法
步骤 1:声明一个名为 findInvertedBinaryTree 的函数，该函数以根值作为参数。
步骤 2:由于步骤 1 中声明的以下函数是递归函数，它会为自己选择一个基例，这样如果根值等于 null ，它就会返回，简单地说明输出中没有可用的树。
步骤 3:遍历左右子分支，直到使用相同函数的递归调用(但使用其左右分支)获得等于 null 的叶节点。
步骤 4:通过临时变量对用户生成的二叉树执行交换子算法，该变量有助于通过自下而上的方法将左子分支数据点与右子分支数据点交换，从底部到根值交换树的子分支中的所有左元素和子元素，直到到达根，根只会被自身交换。
算法代码 - findInvertedBinaryTree 方法
function findInvertedBinaryTree (root) {
if (root === null) return;
let temporaryHold;
findInvertedBinaryTree(root.left);
findInvertedBinaryTree(root.right);
temporaryHold = root.left;
root.left = root.right;
root.right = temporaryHold;
return root
};
console.log(printTree(originalTree));
问题陈述向我们展示了算法的模块化编程，从创建节点到在 BST 中打印节点，然后找到倒置二叉树。
示例
上述算法的组合主代码如下所示:
class Node {
constructor(value){
this.value = value;
this.left = null;
this.right = null;
}
}
const printTree = (root) => {
let listOfTreeElements = [];
let queueOfTreeElements = [root];
while (queueOfTreeElements.length) {
let currentNode = queueOfTreeElements.shift();
listOfTreeElements.push(currentNode.value);
if(currentNode.left) queueOfTreeElements.push(currentNode.left);
if(currentNode.right) queueOfTreeElements.push(currentNode.right);
}
return listOfTreeElements;
}
function findInvertedBinaryTree (root) {
if (root === null) return;
let temporaryHold;
findInvertedBinaryTree(root.left);
findInvertedBinaryTree(root.right);
temporaryHold = root.left;
root.left = root.right;
root.right = temporaryHold;
return root
};
let originalTree = new Node(4);
originalTree.left = new Node(2);
originalTree.right = new Node(7);
originalTree.left.left = new Node(1);
originalTree.left.right = new Node(3);
originalTree.right.left = new Node(9);
originalTree.right.right = new Node(0);
console.log(printTree(originalTree));
console.log(' Inverted Binary Tree :');
console.log(printTree(findInvertedBinaryTree(originalTree)));
输出
输出如下所示，
[ 4, 2, 7, 1, 3, 9, 0 ] Inverted Binary Tree : [ 4, 7, 2, 0, 9, 3, 1 ]
时间和空间复杂度
使用递归方法，每个元素或节点仅遍历一次以进行树反转，这样时间复杂度就降低到 O(n)，而空间复杂度与二叉树的高度或与函数递归调用的次数成正比，该次数等于树的高度，即 O(h)，其中 h 是树的高度。
结论
这就是我们如何通过模块化和逻辑地思考不同的子算法来找到二叉搜索树的镜像来解决上述问题陈述。
