669 : Trim a Binary Search Tree ( leetcode / java )

*해결과정

 

 이진 탐색트리라는 것에 주의한다. 특징으로는 root값은 왼쪽 자식보다 값이 크고 오른쪽 자식보다는 값이 작아야 한다. 이 특징을 이용해 low와 high가 주어졌을 때 유동적으로 이동해야 한다. 이진 탐색트리라는 특성을 제대로 파악하지 못해서 문제푸는데 많은 어려움을 겪었다. 즉, root값이 low값보다 작으면 너무 작은 값이므로 오른쪽 자식으로 이동하고 root값이 high보다 크면 너무 크기 때문에 왼쪽 자식으로 이동한다.

 

class Solution {
    public TreeNode trimBST(TreeNode root, int low, int high) {
        if (root == null) return root;
        if (root.val > high) return trimBST(root.left, low, high);
        if (root.val < low) return trimBST(root.right, low, high);

        root.left = trimBST(root.left, low, high);
        root.right = trimBST(root.right, low, high);
        return root;       
    }
}