.leetcode(700. Search in a Binary Search Tree)

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

 

1. 2022.03.29 시도

소요시간: 3분(recursive), 3분(iterative)

// recursive
class Solution {
    public TreeNode searchBST(TreeNode root, int val) {
        if (root == null) {
            return null;
        }
        
        if (root.val == val) {
            return root;
        }
        
        TreeNode left = searchBST(root.left, val);
        if (left != null) {
            return left;
        }
        TreeNode right = searchBST(root.right, val);
        if (right != null) {
            return right;
        }
        
        return null;
    }
}

// iterative
class Solution {
    public TreeNode searchBST(TreeNode root, int val) {
        if (root == null) {
          return null;
        }

        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()) {
            TreeNode node = queue.poll();
            if (node.val == val) {
                return node;
            }
            
            if (node.left != null){
                queue.offer(node.left);
            }
            
            if (node.right != null){
                queue.offer(node.right);
            }
        }

        return null;
    }
}

풀이 접근 과정

순회해서 노드 찾아서 리턴하면 되겠다.

 

느낀점

• 다른 트리문제와 풀이가 동일했다.
• 좀 더 효율적으로 하려면 BST의 특성을 이용하여 분기처리 해주면 좋다. 왼쪽은 노드값보다 작고 오른족은 노드값보다 크다는 성질을 이용하는 것이다.

---

알고리즘 정리노트: .leetcode(알고리즘 문제풀이 접근)

반응형