将一个二叉树扁平化。
所有扁平化就是：
1
2
3
4
5
|
1
/ \
2 5
/ \ \
3 4 6
|
变为：
1
2
3
4
5
6
7
8
9
10
11
|
1
\
2
\
3
\
4
\
5
\
6
|
Each node’s right child points to the next node of a pre-order traversal.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
|
class Solution {
public:
TreeNode * flattenStep(TreeNode *root) {
if(root->left == NULL && root->right == NULL)
return root;
TreeNode * tmp = NULL;
if(root->right != NULL)
tmp = flattenStep(root->right);
if(root->left != NULL)
root->right = flattenStep(root->left);
else
root->right = NULL;
root->left = NULL;
if(tmp != NULL) {
TreeNode * tmpright = root;
while(tmpright->right != NULL)
tmpright = tmpright->right;
tmpright->right = tmp;
}
return root;
}
void flatten(TreeNode *root) {
if(root == NULL)return;
root = flattenStep(root);
}
};
|