LeetCode 863 : 이진 트리의 모든 노드 거리 K
LeetCode의 "이진 트리의 모든 노드 거리 K"에 대한 두 가지 유사한 솔루션을 게시하고 있습니다. 리뷰를 원하시면 그렇게 해주세요. 감사합니다!
문제
이진 트리 (루트 노드 포함
root),target노드 및 정수 값이 제공K됩니다.
K대상 노드에서 거리가있는 모든 노드의 값 목록을 반환 합니다. 답변은 어떤 순서로든 반환 할 수 있습니다.입력:
root = [3,5,1,6,2,0,8,null,null,7,4],target = 5,K = 2산출:
[7,4,1]설명:
- 대상 노드에서 거리 2 (값 5)에있는 노드의 값은 7, 4, 1입니다.
- 입력 "root"와 "target"은 실제로 TreeNode입니다.
- 위의 입력에 대한 설명은 이러한 개체의 직렬화 일뿐입니다.
노트 :
- 주어진 나무는 비어 있지 않습니다.
- 트리의 각 노드에는 고유 한 값 0 <= node.val <= 500이 있습니다.
- 대상 노드는 트리의 노드입니다.
- 0 <= K <= 1000.
입력 "root"와 "target"은 실제로 TreeNode입니다. 위의 입력에 대한 설명은 이러한 개체의 직렬화 일뿐입니다.
해결책 1
// The following block might slightly improve the execution time;
// Can be removed;
static const auto __optimize__ = []() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
return 0;
}();
// Most of headers are already included;
// Can be removed;
#include <cstdint>
#include <vector>
#include <unordered_map>
#include <unordered_set>
using ValueType = int;
static const struct Solution {
static const std::vector<ValueType> distanceK(
TreeNode* root,
TreeNode* target,
const ValueType K
) {
std::vector<ValueType> res;
std::unordered_map<TreeNode*, TreeNode*> parents;
std::unordered_set<TreeNode*> visited;
getParent(root, parents);
depthFirstSearch(target, K, parents, visited, res);
return res;
}
private:
static const void getParent(
TreeNode* node,
std::unordered_map<TreeNode*, TreeNode*>& parents
) {
if (!node) {
return;
}
if (node->left) {
parents[node->left] = node;
getParent(node->left, parents);
}
if (node->right) {
parents[node->right] = node;
getParent(node->right, parents);
}
}
static const void depthFirstSearch(
TreeNode* node,
const ValueType K,
std::unordered_map<TreeNode*, TreeNode*>& parents,
std::unordered_set<TreeNode*>& visited,
std::vector<ValueType>& res
) {
if (!node) {
return;
}
if (visited.count(node) > 0) {
return;
}
visited.insert(node);
if (!K) {
res.emplace_back(node->val);
return;
}
depthFirstSearch(node->left, K - 1, parents, visited, res);
depthFirstSearch(node->right, K - 1, parents, visited, res);
depthFirstSearch(parents[node], K - 1, parents, visited, res);
}
};
해결 방법 2
// The following block might slightly improve the execution time;
// Can be removed;
static const auto __optimize__ = []() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
return 0;
}();
// Most of headers are already included;
// Can be removed;
#include <cstdint>
#include <vector>
#include <unordered_map>
#include <unordered_set>
using ValueType = int;
static const struct Solution {
const std::vector<ValueType> distanceK(
TreeNode* root,
TreeNode* target,
ValueType K
) {
getParent(root);
depthFirstSearch(target, K);
return res;
}
private:
std::vector<ValueType> res;
std::unordered_map<TreeNode*, TreeNode*> parents;
std::unordered_set<TreeNode*> visited;
const void getParent(
TreeNode* node
) {
if (!node) {
return;
}
if (node->left) {
parents[node->left] = node;
getParent(node->left);
}
if (node->right) {
parents[node->right] = node;
getParent(node->right);
}
}
const void depthFirstSearch(
TreeNode* node,
const ValueType K
) {
if (!node) {
return;
}
if (visited.count(node) > 0) {
return;
}
visited.insert(node);
if (!K) {
res.emplace_back(node->val);
return;
}
depthFirstSearch(node->left, K - 1);
depthFirstSearch(node->right, K - 1);
depthFirstSearch(parents[node], K - 1);
}
};
참고
다음은 LeetCode의 템플릿입니다.
/**
* 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:
vector<int> distanceK(TreeNode* root, TreeNode* target, int K) {
}
};
863. 이진 트리의 모든 노드 거리 K-문제
863. 이진 트리의 모든 노드 거리 K-토론
답변
약 __optimize__
이중 밑줄로 시작하는 식별자 는 예약되어 있습니다. 또한 왜 이것이 일반 함수가 아닌 람다로 작성됩니까? 또한 표준 I / O를 읽고 쓰는 것도 아니므로이 기능은 아무 효과가 없습니다.
클래스 또는 네임 스페이스 외부에서 형식 별칭을 만들지 마십시오.
using ValueType = int매우 일반적인 이름이며 동일한 작업을 수행하는 다른 코드와 충돌 할 수 있으므로 전역 네임 스페이스에서 선언하지 마십시오 . 이 경우에는 이것을 내부에 선언하십시오 struct Solution.
static const 구조체 정의에 영향을주지 않습니다.
한정자 static이며 const의 정의에 영향을주지 않습니다 struct. 다음과 같이 구조체를 정의하고 해당 유형의 변수를 한 번에 선언 할 수 있기 때문에 C ++ 문법에서 허용됩니다.
static const struct foo {
...
} bar;
foo baz;
상기에서, bar이다 static const, 그러나 baz아니다.
const 비 포인터 / 참조 반환 값에는 영향을주지 않습니다.
마찬가지로, const반환되는 포인터 나 참조가 아니면 함수의 반환 값에 영향을주지 않습니다. const값을 항상 비 const변수 에 복사 할 수 있기 때문에 이치에 맞지 않습니다 . 또한 무엇 const void을 의미합니까?
정적 static함수 와 비 멤버 함수
두 가지 변형은 static상태가 클래스 멤버 변수로 유지되는 비 멤버 함수 를 사용하는지 아니면 static스택에 할당되고 다른 멤버 함수에 대한 포인터로 전달되는 상태가있는 멤버 함수 를 사용하는지에 따라 다릅니다 . 둘 다 유효한 접근 방식이지만 실제로 중요하지 않다는 사실은 struct Solution자체 사용이 무의미하다는 것을 알려야합니다 . 실제 응용 프로그램에서는 distanceK()클래스의 구성원이 아닌 함수가 있습니다 . 나는 LeetCode class가 최소한의 변경으로 Java 문제를 C ++에 복사하고 붙여 넣었 기 때문에 당신에게 제공한다고 믿습니다 . 그리고 Java는 함수가 클래스 외부에서 정의되는 것을 허용하지 않습니다.
최적화가 활성화되면 컴파일러는 두 경우 모두 매우 유사한 어셈블리를 생성 할 것입니다.
를 사용하여 std::bitset방문한 노드를 추적 하십시오.
문제는 최대 501 개의 고유 노드 만 있다는 것입니다. 즉, std::bitset를 사용하여 방문한 노드를 추적 할 수 있습니다 . bitset은 64 바이트 만 사용하므로 .NET TreeNode *을 유지하는 다른 모든 오버 헤드는 고사하고 단일에 대해 8 바이트와 비교 합니다 std::unordered_set<TreeNode *>.
많은 메모리 사용을 피하십시오
그렇지 않으면 매우 합리적으로 보이는 알고리즘의 문제는 모든 노드의 부모를 계산해야한다는 것입니다. 그 TreeNode자체 로는 저장할 수 없기 때문에 이제는 unordered_map<TreeNode *, TreeNode *>입력만큼 많은 공간을 차지하는를 유지해야합니다 .
깊이 우선 검색을 수행하면 DFS 함수를 재귀 적으로 호출 할 때 재귀하는 노드의 부모를 알고 있으므로 다음과 같이 함수에 전달할 수 있습니다.
void DFS(Node *node, Node *parent) {
if (!node)
return;
// do something with node and/or parent
DFS(node->left, node);
DFS(node->right, node);
}
문제는 트리의 루트가 아닌 대상 노드에서 DFS를 시작하려고하므로 대상의 부모를 알지 못한다는 것입니다. 그러나 어쨌든 루트에서 시작하도록 알고리즘을 수정 한 다음 대상에 도달하기 위해 얼마나 멀리 내려야했는지 추적 할 수 있습니다. 일단 목표에 도달하면 평소처럼 아래로 재귀하지만, 완료되면 위쪽으로 돌아와서 어떻게 든 목표를 만났다는 신호를 보내야하며, 다른 방법으로 거리 K에서 노드를 찾습니다. 이것은 트리의 일부를 두 번 방문해야한다는 것을 의미 할 수 있지만 이미 현재 알고리즘에서 그렇게하고 있습니다.