极客笔记JavaScript 反转二叉树
问题陈述要求用户给定一个二叉树，你需要找到二叉树元素的镜像图，即反转树分支的对应和并行兄弟节点。简而言之，给定原始二叉树，反转整个二叉树。
问题陈述的输出看起来像是对输入二叉树的倒置函数的总结。
JavaScript中的树是什么
树是一种优化的数据结构之一，用于保存数据，树中的数据点称为节点。树数据结构在现实世界中以树的形式展示。树的顶部数据点称为根节点，树的分支就像现实世界中的树一样，称为子节点，其可以具有递归分支，其有自己的子节点或者没有子节点。
树数据结构对于从单个节点出来的子节点的分支数量没有限制，但数据结构树中存在许多类型的树。
JavaScript中的二叉树是什么
二叉树是一种在JavaScript中的树类型，其中树的每个分支最多包含两个子节点。它也是按时间顺序排序的，树的左侧比根节点具有较小的值，树的右侧比根节点具有较大的值，使树完全平衡。
JavaScript中的倒置二叉树是什么
倒置二叉树是指根据特定规则对树进行倒置，其中二叉树的左子节点成为二叉树的右子节点。对于树的递归子分支，同样适用这个特定条件。
第1步 – 创建一个节点
创建一个二叉搜索树节点的算法如下：
步骤 1： 声明一个名为Node的类，其中使用构造函数以值参数初始化实际数据点。
步骤 2： 构造函数将使用JavaScript中的this关键字将实际数据点初始化为当前上下文和引用，并且还将左侧和右侧指针初始化为null，用于在树中插入数据点的左侧和右侧位置。算法的代码如下：
第2步- 创建一个节点的代码
class Node {
constructor(value){
this.value = value;
this.left = null;
this.right = null;
}
}
第3步- 打印树
该算法用于在使用 createNode 函数创建节点后向用户显示节点，它返回给定节点中的所有值。
步骤 1 ：声明一个名为 printTree 的函数，以用户提供的根值作为其参数作为核心输入。
步骤 2 ：声明一个树元素的列表和队列，使用空数组来初始化列表，使用根作为传递给函数的参数来初始化队列。
步骤 3 ：当队列的长度不小于 0 时，我们需要将第一个元素从索引为 0 的位置取出并使用 JavaScript 中的 push 方法将其重新放回元素列表中。
步骤 4 ：它是算法的递归步骤，用于检查树的左分支是否非空，如果非空，则将左分支的元素推入列表中。
步骤 5 ：它是算法的递归步骤，用于检查树的右分支是否非空，如果非空，则将右分支的元素推入列表中。
第4步- 打印树的代码
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));
这就是问题陈述的方式，展示了如何从创建节点到打印二叉搜索树节点，然后找到倒置的二叉树的模块化编程算法。
示例
以上算法的综合主代码如下所示：
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为树的高度。
结论
这就是我们通过在找到二叉搜索树的镜像时，在不同子算法周围进行模块化和逻辑思考的方法。