Hai tổng trong các BST bằng JavaScript

Vấn đề:

Chúng tôi được yêu cầu viết một hàm JavaScript lấy gốc của hai cây tìm kiếm nhị phân, root1 và root2, làm đối số thứ nhất và thứ hai tương ứng. Đối số thứ ba của hàm là số, đích.

Hàm của chúng ta sẽ trả về True nếu và chỉ khi có một nút trong cây đầu tiên và một nút trong cây thứ hai có giá trị tổng bằng một mục tiêu số nguyên nhất định, ngược lại là false.

Ví dụ:nếu đầu vào của hàm là -

const target = 23;

BST

Sau đó, đầu ra phải là -

const output = true;

Giải thích đầu ra:

Bởi vì tồn tại 6 trong cây đầu tiên và 17 trong cây thứ hai, có tổng là 23.

Ví dụ

Mã cho điều này sẽ là -

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));

Đầu ra

Và đầu ra trong bảng điều khiển sẽ là -

true