Two Sum ใน BST สองต้นใน JavaScript

ปัญหา:

เราต้องเขียนฟังก์ชัน JavaScript ที่รับรูทของต้นค้นหาบाइनนารีสองต้น root1 และ root2 เป็นอาร์กิวเมนต์แรกและสอง อาร์กิวเมนต์ที่สามคือตัวเลข target

ฟังก์ชันควรคืนค่า true ก็ต่อเมื่อมีโหนดในต้นแรกและโหนดในต้นที่สองที่ผลรวมของค่าเท่ากับ target มิฉะนั้นคืนค่า false

ตัวอย่างเช่น หากอินพุตคือ

const target = 23;

BSTs

ผลลัพธ์ควรเป็น

const output = true;

คำอธิบายผลลัพธ์:

เพราะมี 6 ในต้นแรกและ 17 ในต้นที่สอง ซึ่งผลรวมเท่ากับ 23

ตัวอย่างโค้ด

class Node{
  constructor(data) {
    this.data = data;
    this.left = null;
    this.right = null;
  };
};
class BinarySearchTree{
  constructor(){
    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