数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装学
法学JavaScript 中反转二叉树
题目要求用户给定一棵二叉树，找到这棵二叉树的镜像图像，使得树枝的对应和并列的兄弟节点反转。简而言之，就是将给定的原始二叉树作为输入，反转整棵二叉树。
题目的输出看起来像是输入二叉树的反转函数的总结。
什么是 JavaScript 中的树？
树指的是一种优化后的数据结构，用于保存数据，树中存在的数据点被称为节点。树形数据结构会自动像现实世界中的树一样可视化。树的顶部数据点称为根节点，从树中伸出的分支就像现实世界中的树一样，称为子节点，子节点也可以有递归分支，这些分支可能有或没有子节点。
树形数据结构对从单个节点伸出的分支（称为子节点）没有限制，但在数据结构树本身中存在许多类型的树。
什么是 JavaScript 中的二叉树？
二叉树是 JavaScript 中的一种树，其中树的每个分支最多包含两个子节点。它也是按时间顺序排列的，其中树的左侧的值小于根节点，树的右侧的值大于根节点，从而完全平衡树。
什么是 JavaScript 中的反转二叉树？
反转二叉树意味着根据特定规则反转树，其中二叉树的左子节点变成二叉树的右子节点。此特定条件适用于树的递归子分支。
算法 - 创建节点
在二叉搜索树中创建节点的算法如下：
步骤 1：声明一个名为 Node 的类，该类采用一个带 value 参数的构造函数，即其中的实际数据点。
步骤 2：构造函数将使用 JavaScript 中的 this 初始化实际数据点到当前上下文和引用，同时将左右指针初始化为 null，以便在树中插入数据点。c 代码算法 -
算法代码 - 创建节点
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));
插入数据点后，二叉搜索树的输出如下所示：
输出
Binary Search Tree after insertion : [ 4, 2, 7, 1, 3, 9, 0 ]
算法 - findInvertedBinaryTree 方法
步骤 1：声明一个名为 findInvertedBinaryTree 的函数，该函数将根值作为参数。
步骤 2：由于步骤 1 中声明的函数是递归函数，它为自己选择一个基本情况，即如果根值等于 null，则它简单地返回，表明输出中没有可用的树。
步骤 3：遍历左右子分支，直到获得等于 null 的叶子节点，使用同一函数的递归调用，但使用其左右分支。
步骤 4：对用户通过临时变量 temporaryHold 生成的二叉树执行交换子算法，该变量有助于通过自下而上的方法将左子分支数据点与右子分支数据点交换，从底部到根值交换树中存在的子分支中的所有左子节点和子元素，直到到达根，根将只由自身交换。
算法代码 - 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 是树的高度。
结论
这就是我们通过模块化和逻辑地思考查找二叉搜索树镜像图像的不同子算法来解决上述问题陈述的方法。
609 次浏览
