LeetCode 1261. 오염된 두 갈래 나무에서 원소를 찾다
18140 단어 LeetCode#LC 두 갈래 트리
방법 1
먼저 dfs로 위에서 아래로 값을 수정합니다.그리고 어떤 값을 찾았을 때, 서열은 확정되었다.예를 들어 9->4->1->0.그리고 이 서열을 반복적으로 조회합니다.
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class FindElements {
public:
TreeNode* root;
FindElements(TreeNode* root) {
this->root = root;
root->val = 0;
dfs(root);
}
void dfs(TreeNode* root){
if(!root){
return;
}
if(root->left){
root->left->val = 2*root->val+1;
dfs(root->left);
}
if(root->right){
root->right->val = 2*root->val+2;
dfs(root->right);
}
}
bool find(int t) {
stack<int> qs;
while(t>0){
qs.push(t);
t = (t-1)/2;
}
TreeNode* p = root;
while(!qs.empty()){
if(!p){
return false;
}
int x = qs.top();
qs.pop();
if(x==p->val*2+1){
if(p->left)
p = p->left;
else
return false;
}else if(x==p->val*2+2){
if(p->right)
p = p->right;
else
return false;
}else{
return false;
}
}
return true;
}
};
/**
* Your FindElements object will be instantiated and called as such:
* FindElements* obj = new FindElements(root);
* bool param_1 = obj->find(target);
*/
방법 2
층계를 이용하여 두루 돌아다니는 질서정연한 다음에 직접 사용한다
binary_search()
2점 찾기.class FindElements {
public:
vector<int> list;
FindElements(TreeNode* root) {
root->val = 0;
dfs(root);
layerOrder(root);
}
void dfs(TreeNode* root){
if(!root){
return;
}
if(root->left){
root->left->val = 2*root->val+1;
dfs(root->left);
}
if(root->right){
root->right->val = 2*root->val+2;
dfs(root->right);
}
}
void layerOrder(TreeNode* root){
queue<TreeNode*> q;
q.push(root);
while(q.size()){
TreeNode* p = q.front();
q.pop();
list.push_back(p->val);
if(p->left){
q.push(p->left);
}
if(p->right){
q.push(p->right);
}
}
}
bool find(int target) {
return binary_search(list.begin(),list.end(),target);
}
};
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
python 문자열 입력으로 모든 유효한 IP 주소 생성(LeetCode 93번 문제)이 문제의 공식 난이도는 Medium으로 좋아요 1296, 반대 505, 통과율 35.4%를 눌렀다.각 항목의 지표로 말하자면 보기에는 약간 규범에 맞는 것 같지만, 실제로도 확실히 그렇다.이 문제의 해법과 의도는 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.