[LeetCode/700/Java]Search in a Binary Search Tree

[LeetCode/700/Java]Search in a Binary Search Tree

 

풀이

/**
 * 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) {
        if(root == null) return root;
        if(root.val == val) return root;
    	if(root.left == null && root.right == null) return null;
    	
    	TreeNode result = searchBST(root.left, val);
    	if(result == null)
    	    result = searchBST(root.right, val);
    	
        return result;
    }
}

후기

이진트리 탐색 알고리즘입니다.

탐색 순서

1. 트리 노드가 null일 경우 노드를 반환 합니다.
2. 트리 노드의 값이 val과 같을 경우 노드를 반환 합니다.
3. 트리 노드가 가장 안쪽까지 도달했을 경우 null을 반환 합니다.
4. 반환용 트리를 생성해서 좌측 이진트리를 재귀호출합니다.
5. 좌측 이진트리 처리중에 노드의 값이 val과 같은 노드가 발견되지 않았을 경우 우측 노드를 재귀호출합니다.
6. 결과값을 반환합니다.

time complexity O(N)
space complexity O(N)