Code & Func

第32天。

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

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

For example, Given

The flattened tree should look like:

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

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

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

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

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

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

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

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

10
        if(root->left)
11
            root->right = root->left;
12
        root->left = NULL;
13
        root = root->right;
14
    }
15
}