LeetCode 알고리즘 문제 103: 두 갈래 나무의 톱니형 차원 반복 해석
15569 단어 Leetcode 알고리즘 문제 분석
예를 들어 두 갈래 나무[3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
:
[
[3],
[20,9],
[15,7]
]
이 제목은 일반적인 차원 반복 사상과 큰 차이가 없다. 이것은 여기에 두 개의 방향이 필요하다. 모든 설정은 두 개의 창고나 대열을 사용한다. 여기는 창고를 사용하고 각 창고는 한 층의 노드를 저장한 다음에 한 방향에서 출력하고 다른 창고는 다른 층의 노드를 저장한다. 보존할 때 반대로 저장한 다음에 다른 방향에서 출력한다.
C++ 소스 코드:
/**
* 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<vector<int>> zigzagLevelOrder(TreeNode* root) {
vector<vector<int>> res;
if (!root) return res;
vector<int> out;
stack<TreeNode*> s1;
stack<TreeNode*> s2;
s1.push(root);
while(!s1.empty() || !s2.empty()){
while(!s1.empty()){
TreeNode *tmp = s1.top();
s1.pop();
out.push_back(tmp->val);
if(tmp->left) s2.push(tmp->left);
if(tmp->right) s2.push(tmp->right);
}
if(!out.empty()) res.push_back(out);
out.clear();
while(!s2.empty()){
TreeNode *tmp = s2.top();
s2.pop();
out.push_back(tmp->val);
if(tmp->right) s1.push(tmp->right);
if(tmp->left) s1.push(tmp->left);
}
if(!out.empty()) res.push_back(out);
out.clear();
}
return res;
}
};
python3 소스 코드:
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def zigzagLevelOrder(self, root: 'TreeNode') -> 'List[List[int]]':
res = []
if root==None: return res
out = []
s1 = [root]
s2 = []
while len(s1)!=0 or len(s2)!=0:
while len(s1)!=0:
tmp = s1.pop()
out.append(tmp.val)
if tmp.left: s2.append(tmp.left)
if tmp.right: s2.append(tmp.right)
if len(out)!=0: res.append(out)
out = []
while len(s2)!=0:
tmp = s2.pop()
out.append(tmp.val)
if tmp.right: s1.append(tmp.right)
if tmp.left: s1.append(tmp.left)
if len(out)!=0: res.append(out)
out = []
return res
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
LeetCode 알고리즘 문제 73: 매트릭스 제로 분석직접적인 해결 방안 은 O (mn) 의 추가 공간 을 사용 하 는 것 이지 만 이것 은 좋 은 해결 방안 이 아니다. 간단 한 개선 방안 은 O (m + n) 의 추가 공간 을 사용 하 는 것 이지 만 이것 은 가장...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.