[일일 알고리즘 Day 108] 간단한 두 갈래 나무 제목인데 쓰는 방법이 꽤 많아요.
제목 링크
LeetCode 199. 두 갈래 나무의 오른쪽 보기 [1]
제목 설명
두 갈래 나무를 정해서 오른쪽에 서 있는 것을 상상하고 꼭대기에서 끝까지 순서대로 오른쪽에서 볼 수 있는 노드 값을 되돌려줍니다.
예제 1
：
[1,2,3,null,5,null,4]
:
[1,3,4]
：
1
풀다
dfs
dfs ， 。
， 。 ， 。
， ， ， 。
bfs
bfs 。 ， 。
bfs ， ？ pair 깊이 값을 하나 더 저장하지만, 이렇게 하면 좀 쓸데없다.
우리는 매번 대기열에 같은 층의 결점만 저장하고 대기열의 크기를 기록하기만 하면 된다.그리고 순서대로 출대해서 출대 개수가 이전에 기록한 크기에 도달할 때까지 한다.그리고 모든 다음 결점을 동시에 팀에 넣는다.이렇게 하면 이 층의 결점이 모두 출대된 후에 대열에 다음 층의 결점만 남았다는 것을 보장할 수 있다.
코드
dfs（c++）
class Solution {
public:
vector<int> rightSideView(TreeNode* root) {
if (!root) return {};
vector<int> left = rightSideView(root->left);
vector<int> right = rightSideView(root->right);
vector<int> res = {root->val};
for (auto x : right) res.push_back(x);
for (int i = right.size(), sz = left.size(); i < sz; ++i) {
res.push_back(left[i]);
}
return res;
}
};
bfs（c++）
class Solution {
public:
vector<int> rightSideView(TreeNode* root) {
vector<int> res;
queue<TreeNode*> Q;
if (root) Q.push(root);
while (!Q.empty()) {
int sz = Q.size();
while (sz--) {
TreeNode* node = Q.front();
Q.pop();
if (!sz) res.push_back(node->val);
if (node->left) Q.push(node->left);
if (node->right) Q.push(node->right);
}
}
return res;
}
};
참고 자료
[1]
LeetCode 199. 두 갈래 나무의 오른쪽 보기:https://leetcode-cn.com/problems/binary-tree-right-side-view/
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
