JavaScript에서 BST의 두 합

문제:

두 개의 이진 검색 트리 root1 및 root2의 루트를 각각 첫 번째 및 두 번째 인수로 취하는 JavaScript 함수를 작성해야 합니다. 함수에 대한 세 번째 인수는 숫자, 대상입니다.

함수는 첫 번째 트리에 노드가 있고 두 번째 트리에 해당 값의 합이 주어진 정수 대상 노드가 있는 경우에만 True를 반환해야 하고 그렇지 않으면 false를 반환해야 합니다.

예를 들어, 함수에 대한 입력이 -

const target = 23;

BST

그러면 출력은 다음과 같아야 합니다. -

const output = true;

출력 설명:

첫 번째 트리에는 6이 있고 두 번째 트리에는 17이 있으므로 합이 23입니다.

예시

이에 대한 코드는 -

class Node{
   constructor(data) {
      this.data = data;
      this.left = null;
      this.right = null;
   };
};
class BinarySearchTree{
   constructor(){
      // root of a binary seach tree
      this.root = null;
   }
   insert(data){
      var newNode = new Node(data);
      if(this.root === null){
         this.root = newNode;
      }else{
         this.insertNode(this.root, newNode);
      };
   };
   insertNode(node, newNode){
      if(newNode.data < node.data){
         if(node.left === null){
            node.left = newNode;
         }else{
            this.insertNode(node.left, newNode);
         };
      } else {
         if(node.right === null){
            node.right = newNode;
         }else{
            this.insertNode(node.right,newNode);
         };
      };
   };
};
const tree1 = new BinarySearchTree();
tree1.insert(1);
tree1.insert(3);
tree1.insert(4);
tree1.insert(2);
tree1.insert(4);
tree1.insert(5);
tree1.insert(6);
const tree2 = new BinarySearchTree();
tree2.insert(9);
tree2.insert(6);
tree2.insert(11);
tree2.insert(3);
tree2.insert(8);
tree2.insert(10);
tree2.insert(17);
const twoSumBSTs = (root1, root2, target) => {
   if(root1 == null || root2 == null) return false;
   if(root1.data + root2.data == target) return true;
   if(root1.data + root2.data < target) {
      return twoSumBSTs(root1.right, root2, target) || twoSumBSTs(root1, root2.right, target);
   }else{
      return twoSumBSTs(root1.left, root2, target) || twoSumBSTs(root1,
      root2.left, target);
   };
};
const target = 23;
console.log(twoSumBSTs(tree1.root, tree2.root, target));

출력

콘솔의 출력은 -

true