[LeetCode/Easy] 700. Search in a Binary Search Tree

1. Input

1) TreeNode root

2) int val

 

2. Output

1) 이진 탐색 트리인 root에서 노드 값이 val인 subtree를 반환

2) 만약 그런 트리가 없다면 null을 반환

 

3. Constraint

1) 노드 개수의 범위는 [1, 5000]이다.

2) 1 <= Node.val <= 10^7

3) 1 <= val <= 10^7

 

4. Example

Input: root = [4,2,7,1,3], val = 2 -> Output: [2,1,3]

Input: root = [4,2,7,1,3], val = 5 -> Output: []

 

5. Code

1) 첫 코드(2023/05/29)

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode searchBST(TreeNode root, int val) {
        TreeNode ans = null;
        Queue<TreeNode> q = new LinkedList<>();
        q.add(root);
        while(!q.isEmpty()){
            TreeNode c = q.remove();
            if(c.val==val){
                ans = c; break;
            }
            if(c.left!=null)
                q.add(c.left);
            if(c.right!=null)
                q.add(c.right);
        }
        return ans;
    }
}

- 5%, 6%

 

2) 수정해본 코드(2023/05/30)

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode searchBST(TreeNode root, int val) {
        TreeNode c = root;
        while(c!=null){
            if(c.val==val)
                break;
            else if(c.left!=null && c.val>val)
                c = c.left;
            else if(c.right!=null && c.val<val)
                c = c.right;
            else
                c = null;
        }
        return c;
    }
}

- 100%, 6%

 

3) 한번 더 도전해본 코드(2023/05/30)

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode searchBST(TreeNode root, int val) {
        TreeNode c = root;
        while(c!=null){
            if(c.val==val)
                break;
            else if(c.val>val)
                c = c.left;
            else
                c = c.right;
        }
        return c;
    }
}

- 100%, 8%

- c 변수를 이용하지 않고 바로 root를 써도 변화는 없었다.