[LeetCode] Search in a Binary Search Tree - 자바스크립트 풀이

문제 링크

 

1. 접근 방법

 

(1) 이진탐색트리에서 루트를 기준으로 왼쪽 노드의 value는 작은 수, 오른쪽 노드의 value는 큰 수다. 이 특성을 이용해서 재귀로 풀면 된다.

 

(2) 찾는 val이 루트의 value보다 크면 오른쪽을 재귀로 탐색한다.

(3) 찾는 val이 루트의 value보다 작으면 왼쪽을 재귀로 탐색한다.

    if (root.val < val) {
        return searchBST(root.right, val);
    } else {
        return searchBST(root.left, val);
    }

 

(3) edge case 예외처리 해 준다.

    if (!root) return null

 

2. 전체 해답

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @param {number} val
 * @return {TreeNode}
 */
var searchBST = function(root, val) {
    if (!root) return null
    if (root.val === val) return root;
    if (root.val < val) {
        return searchBST(root.right, val);
    } else {
        return searchBST(root.left, val);
    }
};