Flatten Tree(树的变胖)

发表于 | 分类于

Flatten Tree

题目描述：

给定一棵树的头节点，要求将树变成指定的链表形状。具体的描述和例子可以看leetcode网站

解题思路：

最直接的一种思路是将链表中的节点按照一定的顺序放入栈或者队列中，然后按照要求将其重新连接就行。可以从题目中发现是类似树的先序遍历的样纸，所以在将树中节点放入队列的时候可以根据这个规律来实现。

代码如下：

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
class Solution {
public:
    void flatten(TreeNode* root) {
        if (!root) return;
        queue<TreeNode*> q;
        preOrder(root, q);
        //此时队列中保存着树的先序遍历结果
        if (root){
            q.pop();
        }
        //队列的第一个节点肯定是原来的根节点
        while(!q.empty()){
            root->right = q.front();
            //将树的右节点指向现在队列的头结点
            root->left = NULL;
            //改变左侧节点指针
            root = root->right;
            //改变当前的root节点便于继续改变下一个节点的指针
            q.pop();
            //出队
        }
        
    }
    void preOrder(TreeNode* root, queue<TreeNode*> &q){
        if (!root) return;
        q.push(root);
        preOrder(root->left, q);
        preOrder(root->right, q);
        //根据先序遍历的方法将树中的节点放入队列中
    }
};

解题思路2：

当然对于树的题目我们依旧可以使用递归的想法来实现。我们的想法是利用一个指针pre来保存不断移动的当前的位置，然后不断的改变指针的指向即可。

代码实现

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
class Solution {
private:
TreeNode* pre;
    void help(TreeNode* root){
        if (!root) return;
        TreeNode* left = NULL;
        TreeNode* right = NULL;
        if (root->left)
            left = root->left;
            //保存左子树
        if (root->right)
            right = root->right;
            //保存右子树
        pre->right = root;
        pre = pre->right;
        //移动pre到下一个位置
        root->left = NULL;
        //当前的子树的左指针设定为空
        help(left);
        //先遍历左边的子树
        help(right);
        //再遍历右边的子树
    }
    public:
    void flatten(TreeNode* root) {
        pre = new TreeNode(-1);
        help(root);
    }
};

解题思路3

在可以利用递归的方法的情况下，我们也可以利用非递归的思路来解决这个问题。解决的思路比较难描述，可以画一棵简单树按照代码中的思路就可以知道解法。

代码如下:

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:
    void flatten(TreeNode* root) {
        while(root){
            if (root->left && root->right){
            //如果左右子树都非空的情况
                TreeNode* l = root->left;
                //记录当前的左子树
                while(l->right){
                    l = l->right;
                }
                //找到左子树的最右节点
                l->right = root->right;
                //将左子树的最右节点指向root的右节点
            }
            if (root->left)
                root->right = root->left;
                //如果当前的root的左子树不为空，将右子树改变为现在的左子树
            root->left = NULL;
            //当前root的左子树设定为空
            root = root->right;
            //移动root节点到当前的右节点
            
        }
    }
};