目次
まず問題を理解する
問題文には「return the inorder traversal」とあります。
ここで登場する the inorder traversal について理解する必要があります。詳しくは Discussionの投稿 が分かりやすかったのでこちらを参考にしてみてください。DFS Inorder Left -> Node -> Right のところですね。
再帰処理を使用する方法
素直に再帰処理で書いてみます。
class Solution {
public:
vector<int> inorderTraversal(TreeNode* root) {
if (root == nullptr) {
return {};
}
std::vector<int> anser;
for (int val : inorderTraversal(root->left)) {
anser.push_back(val);
}
anser.push_back(root->val);
for (int val : inorderTraversal(root->right)) {
anser.push_back(val);
}
return anser;
}
};範囲for文を使用するとこんな感じで書けます。
時間計算量、空間計算量は共に O(n) です。
一応動きますが、これだと再帰呼び出しする度にvectorのメモリを確保したり、呼び出し元のanserに値を詰めなおしたり、余計なコストが掛かります。
ちょっとだけ最適化するとこんな感じになります。
class Solution {
public:
vector<int> inorderTraversal(TreeNode* root) {
std::vector<int> anser;
inorder(root, anser);
return anser;
}
private:
void inorder(TreeNode* root, std::vector<int>& anser) const {
if (root == nullptr) {
return;
}
inorder(root->left, anser);
anser.push_back(root->val);
inorder(root->right, anser);
}
};繰り返し構文を使用する方法
class Solution {
public:
vector<int> inorderTraversal(TreeNode* root) {
std::vector<int> anser;
TreeNode* current = root;
std::stack<TreeNode> parents;
while (current != nullptr || 1 <= parents.size()) {
if (current != nullptr) {
parents.push(*current);
current = current->left;
} else {
TreeNode parent = parents.top();
parents.pop();
anser.push_back(parent.val);
current = parent.right;
}
}
return anser;
}
};一番左下のNodeを探しながらスタックに詰め、左下(nullptr)に着いたら親Nodeの値を詰め、親Node->rightのNodeで処理を繰り返していく方法です。
せっかく繰り返し構文で書くのだから空間計算量はO(1)になってくれないかなーと願っていましたが、結局スタックを使用する方法しか思い浮かばなかったので、時間計算量、空間計算量は共に再帰処理と同じ(O(n))です。
以上です！