[LeetCode] 653. Two Sum IV - Input is a BST

문제 출처: https://leetcode.com/problems/two-sum-iv-input-is-a-bst/

Two Sum IV - Input is a BST - LeetCode

---

문제

이진 탐색 트리의 root 와 목표 숫자 k 가 주어지면, BST 내에 두 노드의 값의 합이 k인 노드가 존재한다면 true 를 반환하라.

 

예제

Input: root = [5,3,6,2,4,null,7], k = 9
Output: true

Input: root = [5,3,6,2,4,null,7], k = 28
Output: false

---

풀이

이진 탐색 트리의 특성을 아는지, 그 특성을 이용해서 문제를 풀 수 있는지에 대한 문제

 

문제 풀이에 사용될 수 있는 이진 탐색 트리의 특성은 다음과 같다:

• (균형 잡힌) 트리라면, 값 탐색 시 매 단계마다 탐색 범위가 절반으로 줄어든다.
• 이진 탐색 트리를 중위 순회하면 정렬된 배열 값을 얻을 수 있다.

 

이진 탐색 트리의 탐색을 이용한 문제 접근

 

트리에서 임의의 노드를 node[i] 라고 할 때, 트리에서 k - node[i].val 값이 존재하는지 찾는 문제로 접근할 수 있다. 이진트리에서 어떤 값이 존재하는지 탐색하는 것은 다음과 같다.

var findNode = function(root, target) {
    if (root == null) { return false; }
    if (root.val == target) { return true; }
    
    if (target > root.val) {
    	return root.right ? findNode(root.right, target) : false;
    } else {
    	return root.left ? findNode(root.left, target) : false;
    }
}

이제 트리의 모든 노드를 돌면서 k - node[i].val 의 값을 갖는 노드가 트리에 있는지 찾아보는 코드를 작성해보자. 여기서는 BFS 방식을 이용해서 전체 트리를 탐색하도록 하였다.

var findTraget = function(root, k) {
    const q = [root];
    while (q.length) {
        const node = q.shift();
        if (findNode(root, k - node.val)) { return true; }
        
        node.right ? q.push(node.right) : '';
        node.left ? q.push(node.left) : '';
    }
    return false;
}

이 코드들을 제출하기 전에, 한 가지 추가로 고려해야 하는 점이 있다. 아래 그림을 살펴보자.

그림은 k = 8, root = [3, 2, 4, null, null, null, 7] 로 주어졌을 때이다. 노드 4에서 findNode() 의 target은 4 가 된다. 트리 내부를 탐색하면서 노드 값이 4 인 노드를 찾게 되는데 이때 찾아지는 노드는 바로 자기 자신이 된다. 트리 내의 두 개의 노드 합계가 k 가 되어야 하는 것이므로 이 경우는 걸러져야 한다. 그래서 다음과 같이 원래 노드와 비교하는 코드를 추가하는 방식으로 이 문제를 해결하였다.

var findNode = function(root, target, origin) {
    if (root == null) { return false; }
    if (origin != root && root.val == target) { return true; }
    
    if (target > root.val) {
    	return root.right ? findNode(root.right, target, origin) : false;
    } else {
    	return root.left ? findNode(root.left, target, origin) : false;
    }
}

var findTraget = function(root, k) {
    const q = [root];
    while (q.length) {
        const node = q.shift();
        if (findNode(root, k - node.val, node)) { return true; }
        
        node.right ? q.push(node.right) : '';
        node.left ? q.push(node.left) : '';
    }
    return false;
}

 

중위 순회를 이용한 문제 접근(정렬 + 투포인터)

 

이진 탐색 트리를 중위 순회하게 되면, 그 특성상 노드 값이 오름차순으로 정렬된 배열을 얻을 수 있다.

var inorder = function(root, arr) {
    root.left ? inorder(root.left, arr) : '';
    arr.push(root.val);
    root.right ? inorder(root.right, arr) : '';
}

정렬된 배열에서 두 개의 값의 합이 k 인 두 노드를 찾기 위해서 투 포인터 기법을 사용할 수 있다. 이 방법은 이름에서 보이는 것처럼 두 개의 포인터를 이용한 방법으로 다음과 같은 과정으로 진행된다.

1. 두 개의 포인터(left, right)를 선언하고 각각 배열의 시작과 끝을 가리키도록 한다.
2. 두 포인터가 가리키는 원소를 합하고, k 와 비교를 한다.
3. 비교 결과에 따라 다음 행위 중 하나를 선택한다.
   1. k 가 더 크다면? right  = right - 1
   2. k 가 더 작다면? left = left - 1
   3. k 와 같다면? true 반환
4. left 가 right 보다 같거나 커질 때까지 2~3을 반복한다.

var findTarget = function(root, k) {
    const arr = [];
    inorder(root, arr);
    
    let l = 0, r = arr.length-1;
    while (l < r) {
        const sum = arr[l] + arr[r];
        if (sum == k) { return true; }
        
        if (sum > k) {
            r -= 1;
        } else {
            l += 1;
        }
    }
    return false;
};

 

Github: 653.js

GitHub - opwe37/Algorithm-Study