Code & Fun

第32天。

今天的题目是Flatten Binary Tree to Linked List:

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

For example,
Given

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

The flattened tree should look like:

1
2
3
4
5
6
7
8
9
10
11
1
\
2
\
3
\
4
\
5
\
6

通过观察结果,我们可以发现它的顺序其实是一个先序遍历,那么我们可以先对树做一个先序遍历并记录节点指针,然后我们只需要将所有节点连接起来即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void flatten2(TreeNode *root) {
if (root == nullptr) return ;
stack<TreeNode *> st;
vector<TreeNode *> tvec;
while(true) {
while(root){
st.push(root);
tvec.push_back(root);
root = root->left;
}
if (st.empty() ) break;
root = st.top();
st.pop();
root = root->right;
}
int i;
for(i = 0;i < tvec.size() - 1;i++) {
tvec[i]->left = nullptr;
tvec[i]->right = tvec[i+1];
}
tvec[i]->left = nullptr;
tvec[i]->right = nullptr;
}

考虑一下递归的去完成整个问题,我们可以先对左孩子和右孩子做一次flatten,然后再讲他们按照适当的顺序连接起来:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void flatten(TreeNode* root) {
if (root==NULL) return ;
flatten(root->left);
flatten(root->right);
auto right = root->right;
auto left = root->left;
if (left){
root->right = left;
root->left = NULL;
while(left->right)
left = left->right;
left->right = right;
}
}

上面的做法由于每次都需要对左孩子有一个一直往右的遍历,所以耗时还是挺大的,可以加入一个last指针,去表示最后一个被访问的节点的位置,为了保证正确性,我们必须先对右孩子进行flatten再对左孩子进行flatten.

1
2
3
4
5
6
7
8
9
TreeNode *last;
void flatten(TreeNode* root) {
if (root==NULL) return ;
flatten(root->right);
flatten(root->left);
root->right = last;
root->left = nullptr;
last = root;
}

然后是在dicuss中看到的迭代算法:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void flatten(TreeNode *root) {
while (root) {
if (root->left && root->right) {
TreeNode* t = root->left;
while (t->right)
t = t->right;
t->right = root->right;
}

if(root->left)
root->right = root->left;
root->left = NULL;
root = root->right;
}
}

本文首发于Code & Fun