LeetCode - 653. Two Sum IV - Input is a BST in Javascript

이번 알고리즘은 2개의 node value 값의 합이 주어진 k값과 같으면 true를 반환하고 없다면 false를 반환하는 문제이다.

어제에 문제를 풀고 in order로 풀어야겠다는 생각으로 쉽게 다가가서 약간 더럽게 풀었다.(왜그랬을까..)

오늘도 역시 인터넷을 뒤져 찾은 코드와 내 코드를 비교한다.

 

참고 코드 https://velog.io/@timevoyage/leetcode-653-Two-Sum-IV-Input-is-a-BST

[leetcode #653] Two Sum IV - Input is a BST

var findTarget = function(root, k) {
  const set = [];
  
  return traverseTree(root, k);
  
  function traverseTree(root, k) {
    if (!root) return false;
    
    if (set.includes(root.val)) {
      return true;
    }
    
    const substractedNum = k - root.val;
    set.push(substractedNum);
    
    return traverseTree(root.left, k) || traverseTree(root.right, k);
  }
 }

인터넷에서 찾은 코드의 전략은 다음과 같다.

set이라는 배열을 세팅한다. 여기에는 k값과 현재 root 값을 빼준 값을 push 한다. 

예를 들어 아래와 같은 노드가 있다.

현재 root는 5라고 하자 k는 8이라고 가정하자.

8-5 ===> 3을 set에 넣어준다.

다시 재귀로 traverseTree(root.left, k)를 해주면 

set은 3을 가지고 있고 현재 root값은 3이므로 true를 반환하게 된다.

이런 전략으로 문제를 푼다. 정말 이마를 탁 치게 된다.

 

내코드

var findTarget = function(root, k) {
  let current = root;
  const sortedTree = inoderTree(current);
  
  if (sortedTree.length === 1) return false;

  for (let i = 0; i < sortedTree.length - 1; i++) {
    for (let j = 1; j < sortedTree.length ; j++) {
      if (i < j && sortedTree[i] + sortedTree[j] === k) return true;
      if (i === sortedTree.length - 2 && j === sortedTree.length - 1) return false;
    }
  }
  
  function inoderTree(current, acc = []) {
    if (!current) return;
    if (current.left) inoderTree(current.left, acc);
    acc.push(current.val);
    if (current.right) inoderTree(current.right, acc);
      
    return acc;
  }
};

내 코드의 전략은 inorder로 정렬하고 이중 for문을 돌려 모든 값을 더해보는 것이다. 좀 무식한 방법이지만 통과는 했다..

 

끝!