LeetCode-114. ツリーをチェーンテーブルに展開
114.ツリーをチェーンテーブルに展開
難易度は中等468
ツリーを指定し、その場で単一チェーンテーブルに展開します.
例えば、所与のツリー
次のように展開します.
今日は外を走って、ぬれねずみになった.
夜は店を変えてご飯を食べに行きます.
難易度は中等468
ツリーを指定し、その場で単一チェーンテーブルに展開します.
例えば、所与のツリー
1
/ \
2 5
/ \ \
3 4 6
次のように展開します.
1
\
2
\
3
\
4
\
5
\
6
今日は外を走って、ぬれねずみになった.
夜は店を変えてご飯を食べに行きます.
#include
#include
#include
using namespace std;
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode() : val(0), left(nullptr), right(nullptr) {}
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
class Solution {
public:
void flatten(TreeNode* root) {
if (root == NULL)
return;
queue m_queue;
backtrace(root, m_queue);
TreeNode* tmp = root;
int length = m_queue.size();
for (int i = 0; i < length; i++) {
tmp->left = NULL;
tmp->right = m_queue.front();
tmp = tmp->right;
m_queue.pop();
}
tmp->right = NULL;
}
private:
void backtrace(TreeNode *root, queue & m_q) {
if (root) {
m_q.push(root);
if (root->left) {
backtrace(root->left, m_q);
}
if (root->right) {
backtrace(root->right, m_q);
}
}
}
};
int main() {
TreeNode* p = new TreeNode(0);
Solution* ps = new Solution();
ps->flatten(p);
while (p) {
cout << p->val << endl;
p = p->right;
}
return 0;
}