2018年4月15日 下午3:54
Flatten Binary Tree to Linked List - LeetCode
- 修改数据本身
- generate的输入是：i代表一颗要处理的子树的根节点
- generate的输出是：last代表返回这课子树的子树的最后一个节点
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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
void flatten(TreeNode* root) {
if(root == NULL)return ;
TreeNode *last = NULL;
generate(root, last);
}
private:
//遍历每个节点。求出当前节点的左右两边的前序链表，然后拼接在一起。
//这个不是遍历这么简单了，而是要在遍历的同时改变原始数据。
//generate的输入是：i代表一颗要处理的子树的根节点
//generate的输出是：last代表返回这课子树的子树的最后一个节点
void generate(TreeNode *i, TreeNode *&last){
last = i;
if(i->left == NULL && i->right == NULL){
return;
}
TreeNode *left = i->left;
TreeNode *right = i->right;
//填上这两个数据
TreeNode *left_last = NULL;
TreeNode *right_last = NULL;
//求左右两边，填left_last,right_last
if(left){
generate(left, left_last);
//重新构造数据格式
i->left = NULL;
i->right = left;
last = left_last;
}
if(right){//这里不可以使用i->right，我们在上一步中已经更改了i的指向。这道题就是让更改原始数据，所有这点要小心
generate(right, right_last);
last->right = right;
last = right_last;
}
}
};