[JAVA] LeetCode - Trim a Binary Search Tree - 669

문제내용

https://leetcode.com/problems/trim-a-binary-search-tree/

Trim a Binary Search Tree - LeetCode

Given the root of a binary search tree and the lowest and highest boundaries as low and high, trim the tree so that all its elements lies in [low, high]. Trimming the tree should not change the relative structure of the elements that will remain in the tree (i.e., any node's descendant should remain a descendant). It can be proven that there is a unique answer.

Return the root of the trimmed binary search tree. Note that the root may change depending on the given bounds.

 

Example 1:

Input: root = [1,0,2], low = 1, high = 2
Output: [1,null,2]

Example 2:

Input: root = [3,0,4,null,2,null,null,1], low = 1, high = 3
Output: [3,2,null,1]

 

Constraints:

• The number of nodes in the tree in the range [1, 104].
• 0 <= Node.val <= 104
• The value of each node in the tree is unique.
• root is guaranteed to be a valid binary search tree.
• 0 <= low <= high <= 104

---

문제 접근 방법

재귀 너무 어려운거같다...문제를 보고 이문제를 어떻게 풀어야할지 생각만 30분정도 했는데 내머리가 나쁜건지 문제이해도 제대로 안됐다;; 그래서 다른 분의 코드를 보고 풀었따.... 최대한 이해한대로 설명해보면

 

제일 첫번째 루트노드를 시작으로해서 단말노드까지 모두 탐색을 해야한다.

다만 조건에 low~high 사이에 노드들만 반환하는 것이기 때문에 중간에 low~high에 속한 노드들만 탐색하게 해주는 처리가 필요하다. 이 조건을 쉽게 구현하기 위해서는 이진탐색트리의 특징을 이용하면된다.

이진 탐색 트리는 루트노드 기준으로

왼쪽은 무조건 루트노드보다 작은노드이고

오른쪽 무조건 루트노드보다 큰노드이다.

 

따라서

현재 루트노드의 값 < low 이면 low의 값은 무조건 현재 루트노드의 오른쪽에 있기 때문에 왼쪽 서브트리는 고려할 필요가 없다.

현재 루트노드의 값 > high 이면 high의 값은 무조건 현재 루트노드의 왼쪽에 있기 때문에 오른쪽 서브트리는 고려할 필요가 없다.

 

그리고

low<= 현재 루트노드의 값 <= high 라면 왼쪽,오른쪽 모든 서브트리를 탐색해줘야한다.

 

기본적인 로직은 위와같고 이를 재귀적으로 구현해내면 된다... 이게 어렵지...ㅠ

코드를 보자.

 

---

풀이

public class Solution {
	public TreeNode trimBST(TreeNode root, int low, int high) {
		if(root==null) return null;//root가 null이면 더이상 탐색할 필요없음.
        
		//오른쪽 서브트리만 고려
        if(root.val<low) return trimBST(root.right, low, high);
        //왼쪽 서브트리만 고려
        if(root.val>high) return trimBST(root.left, low, high);
        
        //low~high 사이일땐 왼쪽,오른쪽 서브트리 둘다 고려
        root.left = trimBST(root.left, low, high);
        root.right = trimBST(root.right, low, high);
        return root;
    }
}

---

마치며

코드 자체는 너무 간단한데... 저런 재귀적인 생각을 해내는게 너무 어려운 과제다..

나에게 재귀는 아직도 미지의 세계인거 같은 느낌 ㅠㅠ