1. 二叉树から文字列の生成
アイデア：通常の前順再帰遍歴に基づいて、右部分木が空の場合を考慮する。
class Solution {
public:
string tree2str(TreeNode* root) {
if (root == nullptr) return "";
if (root->left == nullptr && root->right == nullptr) return to_string(root->val);
if (root->right == nullptr)
return to_string(root->val) + "(" + tree2str(root->left) + ")";
return to_string(root->val) + "(" + tree2str(root->left) + ")(" + tree2str(root->right) + ")";
}
};
2. 二叉树のレベル順遍歴
アイデア：
方法一 (BFS)
キューを使用して各レベルのノードを処理する。
方法二 (DFS)
深さごとのノードを格納する配列を定義する。
方法一: BFS
class Solution {
public:
vector<vector<int>> levelOrder(TreeNode* root) {
vector<vector<int>> vv;
if (root == nullptr) return vv;
queue<TreeNode*> q;
q.push(root);
while (!q.empty()) {
vector<int> v;
int size = q.size();
while (size--) {
TreeNode* node = q.front();
q.pop();
v.emplace_back(node->val);
if (node->left) q.push(node->left);
if (node->right) q.push(node->right);
}
vv.push_back(v);
}
return vv;
}
};
方法二: DFS
class Solution {
public:
void dfs(TreeNode* root, int k, vector<vector<int>>& ans) {
if (root == nullptr) return;
if (k == ans.size()) ans.push_back(vector<int>());
ans[k].push_back(root->val);
dfs(root->left, k + 1, ans);
dfs(root->right, k + 1, ans);
}
vector<vector<int>> levelOrder(TreeNode* root) {
vector<vector<int>> ans;
dfs(root, 0, ans);
return ans;
}
};
3. 二叉树のレベル順遍歴II
アイデア：
下から上に各レベルのノード値を出力するため、結果リストの先頭に追加する。
方法一: BFS
class Solution {
public:
vector<vector<int>> levelOrderBottom(TreeNode* root) {
vector<vector<int>> vv;
if (root == nullptr) return vv;
queue<TreeNode*> q;
q.push(root);
while (!q.empty()) {
vector<int> v;
int n = q.size();
while (n--) {
TreeNode* Node = q.front();
q.pop();
v.push_back(Node->val);
if (Node->left) q.push(Node->left);
if (Node->right) q.push(Node->right);
}
vv.push_back(v);
}
reverse(vv.begin(), vv.end());
return vv;
}
};
方法二: DFS
class Solution {
public:
void dfs(TreeNode* root, int k, vector<vector<int>>& ans) {
if (root == nullptr) return;
if (k == ans.size()) ans.push_back(vector<int>());
ans[k].push_back(root->val);
dfs(root->left, k + 1, ans);
dfs(root->right, k + 1, ans);
}
vector<vector<int>> levelOrderBottom(TreeNode* root) {
vector<vector<int>> ans;
dfs(root, 0, ans);
reverse(ans.begin(), ans.end());
return ans;
}
};
4. 二叉树の最近共通祖先
アイデア：
2つのノード p と q は次の2つの場合に分かれる：
- p と q が同じ部分木にある
- p と q が異なる部分木にある
根ノードから始めて、左右の部分木を再帰的に調べる。
class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if (root == nullptr || root == p || root == q) return root;
TreeNode* l = lowestCommonAncestor(root->left, p, q);
TreeNode* r = lowestCommonAncestor(root->right, p, q);
if (l && r) return root;
return l ? l : r;
}
};
5. 二叉探索木と双方向リスト
アイデア：
二叉探索木の中間順遍歴は昇順になるため、中間順でノードを連結する。
class Solution {
public:
TreeNode* preNode;
TreeNode* Convert(TreeNode* pRootOfTree) {
if (pRootOfTree == nullptr) return pRootOfTree;
TreeNode* p = pRootOfTree;
while (p->left) p = p->left;
Inorder(pRootOfTree);
return p;
}
void Inorder(TreeNode* root) {
if (root == nullptr) return;
Inorder(root->left);
root->left = preNode;
if (preNode) preNode->right = root;
preNode = root;
Inorder(root->right);
}
};
6. 前順遍歴（非再帰）
class Solution {
public:
vector<int> preorderTraversal(TreeNode* root) {
vector<int> ans;
if (root == nullptr) return ans;
stack<TreeNode*> st;
TreeNode* node = root;
while (!st.empty() || node != nullptr) {
while (node != nullptr) {
ans.push_back(node->val);
st.push(node);
node = node->left;
}
node = st.top();
st.pop();
node = node->right;
}
return ans;
}
};
7. 中間順遍歴（非再帰）
class Solution {
public:
vector<int> inorderTraversal(TreeNode* root) {
vector<int> ans;
stack<TreeNode*> s;
while (root != nullptr || !s.empty()) {
while (root != nullptr) {
s.push(root);
root = root->left;
}
root = s.top();
s.pop();
ans.push_back(root->val);
root = root->right;
}
return ans;
}
};
8. 後順遍歴（非再帰）
class Solution {
public:
vector<int> postorderTraversal(TreeNode* root) {
vector<int> ans;
stack<TreeNode*> s;
TreeNode* pre = nullptr;
while (root != nullptr || !s.empty()) {
while (root != nullptr) {
s.push(root);
root = root->left;
}
root = s.top();
s.pop();
if (root->right == nullptr || root->right == pre) {
ans.push_back(root->val);
pre = root;
root = nullptr;
} else {
s.push(root);
root = root->right;
}
}
return ans;
}
};
9. 前順と中間順から二叉树を構築
class Solution {
private:
unordered_map<int, int> pos;
public:
TreeNode* dfs(const vector<int>& preorder, const vector<int>& inorder, int pl, int pr, int il, int ir) {
if (pl > pr) return nullptr;
int k = pos[preorder[pl]];
TreeNode* root = new TreeNode(preorder[pl]);
int len = k - il;
root->left = dfs(preorder, inorder, pl + 1, pl + len, il, k - 1);
root->right = dfs(preorder, inorder, pl + len + 1, pr, k + 1, ir);
return root;
}
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
int n = preorder.size();
for (int i = 0; i < n; ++i) {
pos[inorder[i]] = i;
}
return dfs(preorder, inorder, 0, n - 1, 0, n - 1);
}
};
10. 中間順と後順から二叉树を構築
class Solution {
public:
unordered_map<int, int> pos;
TreeNode* dfs(vector<int>& inorder, vector<int>& postorder, int il, int ir, int pl, int pr) {
if (il > ir) return nullptr;
int k = pos[postorder[pr]];
TreeNode* root = new TreeNode(postorder[pr]);
root->left = dfs(inorder, postorder, il, k - 1, pl, pl + k - 1 - il);
root->right = dfs(inorder, postorder, k + 1, ir, pl + k - il, pr - 1);
return root;
}
TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
int n = inorder.size();
for (int i = 0; i < n; i++) {
pos[inorder[i]] = i;
}
return dfs(inorder, postorder, 0, n - 1, 0, n - 1);
}
};
11. 前順と後順から二叉树を構築
class Solution {
public:
int preIndex = 0, posIndex = 0;
TreeNode* constructFromPrePost(vector<int>& preorder, vector<int>& postorder) {
TreeNode* root = new TreeNode(preorder[preIndex++]);
if (root->val != postorder[posIndex])
root->left = constructFromPrePost(preorder, postorder);
if (root->val != postorder[posIndex])
root->right = constructFromPrePost(preorder, postorder);
posIndex++;
return root;
}
};
12. 完全二叉树の後順遍歴からレベル順遍歴への変換
#include <iostream>
#include <vector>
using namespace std;
void buildLevelOrder(vector<int>& level, int index, int start, int end, const vector<int>& post) {
if (start > end) return;
level[index] = post[end];
if (start == end) return;
int m = end - start + 1;
int leftSize = m / 2;
buildLevelOrder(level, 2 * index + 1, start, start + leftSize - 1, post);
buildLevelOrder(level, 2 * index + 2, start + leftSize, end - 1, post);
}
int main() {
int n;
cin >> n;
vector<int> post(n);
for (int& num : post) {
cin >> num;
}
vector<int> level(n);
buildLevelOrder(level, 0, 0, n - 1, post);
for (int num : level) {
cout << num << " ";
}
return 0;
}
1. 先順排列の求める
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
string in, post;
void dfs1(int il, int ir, int pl, int pr) {
if (il > ir) return;
char root = post[pr];
cout << root;
int pos;
for (pos = il; pos <= ir; pos++) {
if (in[pos] == root) break;
}
dfs1(il, pos - 1, pl, pl + pos - 1 - il);
dfs1(pos + 1, ir, pl + pos - il, pr - 1);
}
void dfs2(string s1, string s2) {
int len1 = s1.length();
int len2 = s2.length();
if (len1 <= 0) return;
char root = s2[len2 - 1];
cout << root;
int pos = s1.find(root);
dfs2(s1.substr(0, pos), s2.substr(0, pos));
dfs2(s1.substr(pos + 1), s2.substr(pos, len1 - pos - 1));
}
int main() {
cin >> in >> post;
int n = in.size();
//dfs1(0, n - 1, 0, n - 1);
dfs2(in, post);
return 0;
}
2. 中間順と後順からレベル順を出力
#include <iostream>
#include <queue>
#include <string>
using namespace std;
const int N = 35;
int b[N], c[N];
int l[N], r[N];
int n;
queue<int> q;
int dfs(int x1, int y1, int x2, int y2) {
if (x1 > y1) return 0;
int pos = x1, root = c[y2];
while (b[pos] != root) pos++;
l[root] = dfs(x1, pos - 1, x2, x2 + pos - x1 - 1);
r[root] = dfs(pos + 1, y1, x2 + pos - x1, y2 - 1);
return root;
}
void bfs(int root) {
int flag = 0;
q.push(root);
while (!q.empty()) {
int i = q.front();
q.pop();
if (flag) printf(" %d", i);
else {
flag = 1;
printf("%d", i);
}
if (l[i] != 0) q.push(l[i]);
if (r[i] != 0) q.push(r[i]);
}
}
int main() {
cin >> n;
for (int i = 0; i < n; i++) cin >> c[i];
for (int i = 0; i < n; i++) cin >> b[i];
int root = dfs(0, n - 1, 0, n - 1);
bfs(root);
return 0;
}
3. 中間順列
class Solution {
public:
int len = 0;
void dfs(vector<int>& pre, int pl, int pr, vector<int>& suf, int sl, int sr, vector<int>& ans) {
if (pl > pr || sl > sr) return;
if (pl == pr) {
ans[len++] = pre[pl];
return;
}
int pos = -1;
for (int i = sl; i <= sr; i++) {
if (suf[i] == pre[pl + 1])
pos = i;
}
dfs(pre, pl + 1, pos - sl + pl + 1, suf, sl, pos, ans);
ans[len++] = pre[pl];
dfs(pre, pos - sl + pl + 2, pr, suf, pos + 1, sr - 1, ans);
}
vector<int> solve(int n, vector<int>& pre, vector<int>& suf) {
vector<int> ans(n);
dfs(pre, 0, n - 1, suf, 0, n - 1, ans);
return ans;
}
};
1. N 叉树のレベル順遍歴
class Solution {
public:
vector<vector<int>> levelOrder(Node* root) {
vector<vector<int>> ans;
if (root == nullptr) return ans;
queue<Node*> q;
q.push(root);
while (!q.empty()) {
vector<int> arr;
int size = q.size();
while (size--) {
Node* node = q.front();
q.pop();
arr.emplace_back(node->val);
for (Node* child : node->children) {
if (child != nullptr) q.push(child);
}
}
ans.emplace_back(arr);
}
return ans;
}
};
2. 二叉树のジグザグ形レベル順遍歴
class Solution {
public:
vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
vector<vector<int>> ans;
if (root == nullptr) return ans;
queue<TreeNode*> q;
q.push(root);
int cnt = 0;
while (!q.empty()) {
vector<int> arr;
int size = q.size();
cnt++;
while (size--) {
TreeNode* node = q.front();
q.pop();
arr.emplace_back(node->val);
if (node->left) q.push(node->left);
if (node->right) q.push(node->right);
}
if (cnt % 2 == 0) reverse(arr.begin(), arr.end());
ans.emplace_back(arr);
}
return ans;
}
};
3. 二叉树の最大幅
class Solution {
public:
int widthOfBinaryTree(TreeNode* root) {
vector<pair<TreeNode*, unsigned int>> q;
q.push_back({root, 1});
unsigned int ret = 0;
while (!q.empty()) {
auto& [x1, y1] = q[0];
auto& [x2, y2] = q.back();
ret = max(ret, y2 - y1 + 1);
vector<pair<TreeNode*, unsigned int>> tmp;
for (auto& [x, y] : q) {
if (x->left) tmp.push_back({x->left, y * 2});
if (x->right) tmp.push_back({x->right, y * 2 + 1});
}
q = tmp;
}
return ret;
}
};
4. 各行の最大値を見つける
class Solution {
public:
vector<int> largestValues(TreeNode* root) {
vector<int> ret;
if (root == nullptr) return ret;
queue<TreeNode*> q;
q.push(root);
while (!q.empty()) {
int ans = INT_MIN, size = q.size();
while (size--) {
TreeNode* node = q.front();
q.pop();
ans = max(ans, node->val);
if (node->left) q.push(node->left);
if (node->right) q.push(node->right);
}
ret.emplace_back(ans);
}
return ret;
}
};