Runtime: 144 ms, faster than93.49%ofC++online submissions forN-ary Tree Postorder Traversal.
Memory Usage: 32.3 MB, less than87.53%ofC++online submissions forN-ary Tree Postorder Traversal.
Should think about iterate solving
LeetCode #590
Q.
Given an n-ary tree, return thepostordertraversal of its nodes' values.
For example, given a3-arytree:
N-진 트리에서, 후위수식으로 순회해서 값을 읽어봐라
예를들면, 3진트리는 아래와 같다:
Return its postorder traversal as:[5,6,3,2,4,1].
Note:
Recursive solution is trivial, could you do it iteratively?
노트:
재귀는 진부하고, 반복문으로 풀어봐라?
풀고나서 문제 옮겨적다가 봄..
//postorder means 후위수식 12*
// Process //1. Input root node pointer //2. Make returnVector //3. Iterate from begin to the end of children (*Node) // 3.1. Call recursivePreorder method //4. Put val in the returnVector //5. Return returnVector
// recursivePostorder //1. Input returnVector //2. Iterate from begin to the end (*Node) // 2.1. Call recursiveVector //3. Put val in the returnVector
// 처리과정
//1. 루트노드 입력받는다.
//2. 결과벡터 만들어둔다.
//3. 노드 안의 벡터 전체 반복한다.
// 3.1. 재귀함수 콜한다.
//4. 노드값 벡터에 넣는다.
//5. 채워진 결과벡터 반환한다.
// resursivePreorder (재귀함수)
//1. 노드와 리턴벡터 입력받는다.
//2. 노드 안의 벡터 전체 반복한다.
// 2.1. 재귀함수 콜한다.
//3. 노드값 벡터에 넣는다.
Code.. lemme see example code!!!
코드.. 예제코드를 보자!!!
class Solution {
public:
vector<int> postorder(Node* root) {
vector<int> returnVector;
if (root != 0) {
for (int i = 0; i < root->children.size(); ++i) {
recursivePostorder(root->children[i], returnVector);
}
returnVector.push_back(root->val);
}
return returnVector;
}
private:
void recursivePostorder(Node* node, vector<int>& returnVector) {
for (int i = 0; i < node->children.size(); ++i) {
recursivePostorder(node->children[i], returnVector);
}
returnVector.push_back(node->val);
}
};
