## 题目描述

Given a binary tree, flatten it to a linked list in-place.

For example,
Given

``````         1
/ \
2   5
/ \   \
3   4   6
``````

The flattened tree should look like:

``````   1
\
2
\
3
\
4
\
5
\
6
``````

click to show hints.

Hints:

If you notice carefully in the flattened tree, each node's right child points to the next node of a pre-order trave

## 代码

``````class Solution {
public:
void flatten(TreeNode *root) {
if (!root) return;
if (root->left) flatten(root->left);
if (root->right) flatten(root->right);
TreeNode *tmp = root->right;
root->right = root->left;
root->left = NULL;
while (root->right) root = root->right;
root->right = tmp;
}
};
``````

``````     1
/ \
2   5
/ \   \
3   4   6

1
/ \
2   5
\   \
3   6
\
4

1
\
2
\
3
\
4
\
5
\
6
``````

``````class Solution {
public:
void flatten(TreeNode *root) {
TreeNode *cur = root;
while (cur) {
if (cur->left) {
TreeNode *p = cur->left;
while (p->right) p = p->right;
p->right = cur->right;
cur->right = cur->left;
cur->left = NULL;
}
cur = cur->right;
}
}
};
``````

``````     1
/ \
2   5
/ \   \
3   4   6

1
\
2
/ \
3   4
\
5
\
6

1
\
2
\
3
\
4
\
5
\
6
``````

``````class Solution {
public:
void flatten(TreeNode* root) {
if (!root) return;
stack<TreeNode*> s;
s.push(root);
while (!s.empty()) {
TreeNode *t = s.top(); s.pop();
if (t->left) {
TreeNode *r = t->left;
while (r->right) r = r->right;
r->right = t->right;
t->right = t->left;
t->left = NULL;
}
if (t->right) s.push(t->right);
}
}
};
``````

评论
0 评论