反转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