다음과 같이 표현되는 이진 트리가 있다고 가정합니다. -
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 for binary tree
class BinaryTree{
constructor(){
// root of the binary tree
this.root = null;
};
insert = (data) => {
// creating a new node with data
const newNode = new Node(data);
// if root is null, then this node will be the root
if(this.root === null){
this.root = newNode;
}else{
// otherwise we find the correct position to insert this node
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);
}
}
};
// function to invert the binary tree
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);
// original right to left traversal
Tree.traverse(Tree.root);
Tree.invert(Tree.root);
console.log('after inversion');
// traversal right to left after inversion
Tree.traverse(Tree.root); 뒤에 왼쪽 출력
콘솔의 출력은 -
9 7 6 4 3 2 1 after inversion 1 2 3 4 6 7 9