[Dart] 700. Search in a Binary Search Tree

1. 문제

https://leetcode.com/problems/search-in-a-binary-search-tree/description/?envType=study-plan-v2&envId=leetcode-75

 

 

 

2. 요구사항

1) 주어진 이진 탐색 트리(Binary Search Tree)에서 val값을 가진 노드를 찾는다.

2) 그 노드를 루트로 하는 서브 트리를 반환한다.

3) 값이 없으면 null을 반환한다.

 

 

 

3. 코드

이진 탐색 트리의 특징은 다음과 같다.

• 현재 노드 > 왼쪽 자식 노드
• 현재 노드 < 오른쪽 자식 노드
• 노드의 값은 모두 고유(unique)

 

class Solution {
   // root - 현재 탐색 중인 노드 (루트부터 시작)
   // val - 찾고자 하는 값
  TreeNode? searchBST(TreeNode? root, int val) {
    // 현재 노드가 null이면 null 반환
    if (root == null) {
      return null;
    }

    // 현재 노드의 값이 찾는 값과 같으면 이 노드를 반환
    if (root.val == val) {
      return root;

    // 찾는 값이 현재 노드보다 작으면 왼쪽 서브트리로 재귀 호출
    } else if (val < root.val) {
      return searchBST(root.left, val);

    // 찾는 값이 현재 노드보다 크면 오른쪽 서브트리로 재귀 호출
    } else {
      return searchBST(root.right, val);
    }
  }
}