Hai tổng trong BST trong JavaScript

Mô tả vấn đề

Chúng ta cần viết hàm JavaScript nhận vào gốc của hai cây tìm kiếm nhị phân root1, root2 làm đối số 1, 2. Đối số 3 là số target.

Hàm trả về true nếu và chỉ nếu tồn tại một nút trong cây 1 và một nút trong cây 2 có tổng giá trị bằng target, ngược lại false.

Ví dụ, nếu đầu vào là:

const target = 23;

BSTs

Thì đầu ra nên là:

const output = true;

Giải thích đầu ra

Vì tồn tại 6 trong cây 1 và 17 trong cây 2, tổng = 23.

Ví dụ minh họa

Mã thực hiện (duyệt BST hai con trỏ):

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

Đầu ra

Kết quả trong console sẽ là:

true