Runtime: 44 ms, faster than95.08%ofC++online submissions forSearch in a Binary Search Tree.
Memory Usage: 29.2 MB, less than53.66%ofC++online submissions forSearch in a Binary Search Tree.
Two codes, using return or using address pointer
두가지 코드, 반환값 사용한거랑 포인터 사용한거
LeetCode #700
Q.
Given the root node of a binary search tree (BST) and a value. You need to find the node in the BST that the node's value equals the given value. Return the subtree rooted with that node. If such node doesn't exist, you should return NULL.
주어진 2진탐색트리의 루트노드와, 찾는 정수값이 있다. 주어진 값을 이진탐색트리의 노드에서 찾아라. 찾은 노드의 하위 노드들을 포함하는 트리를 반환해라. 주어진 값과 같은 노드가 없으면, NULL을 반환해라.
In the example above, if we want to search the value5, since there is no node with value5, we should returnNULL.
Note that an empty tree is represented byNULL, therefore you would see the expected output (serialized tree format) as [], notnull.
위의 예에서, 만약 우리가 정수값 5를 찾고 있었다면, 해당하는 노드가 없으므로, NULL 을 반환한다. NULL 로 표현되는 빈 트리는, [] 이다, null 이 아니다.
Process
// Process //1. Input root node
//2. Search node having same int value
//3. Return that node pointer
// 처리과정
//1. 루트노드 입력받는다.
//2. 찾는 값이 있는 노드를 찾는다.
//3. 찾은 노드를 반환한다.
Code.. lemme see example code!!!
코드.. 예제코드를 보자!!!
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
TreeNode* searchBST(TreeNode* root, int val) {
TreeNode* returnNode = 0;
returnNode = recursiveSearch(returnNode, root, val);
return returnNode;
}
private:
TreeNode* recursiveSearch(TreeNode* returnNode, TreeNode* node, int val) {
if (node != 0) {
if (node->val == val && returnNode == 0) {
returnNode = node;
}
else {
returnNode = recursiveSearch(returnNode, node->left, val);
if (returnNode == 0)
returnNode = recursiveSearch(returnNode, node->right, val);
}
}
return returnNode;
}
};
class Solution {
public:
TreeNode* searchBST(TreeNode* root, int val) {
TreeNode* returnNode = new TreeNode(0);
recursiveSearch(returnNode, root, val);
if (returnNode->val != 0)
return returnNode;
else
return 0;
}
private:
void recursiveSearch(TreeNode* returnNode, TreeNode* node, int val) {
if (node != 0) {
if (node->val == val) {
*returnNode = *node;
}
else {
recursiveSearch(returnNode, node->left, val);
recursiveSearch(returnNode, node->right, val);
}
}
}
};
