题目描述

二叉树展开为链表。

样例

例如，给定二叉树

    1
   / \
  2   5
 / \   \
3   4   6
将其展开为：

1
 \
  2
   \
    3
     \
      4
       \
        5
         \
          6

算法1

(迭代模拟) $O(n)$

一种类似morris遍历的小套路。

时间复杂度

每个节点被遍历$O(1)$次，访问了$O(n)$个节点，所以总时间复杂度$O(n)$。

参考文献

C++ 代码

class Solution {
public:
    void flatten(TreeNode* root) {
        if (!root) return;
        TreeNode *p = root, *q = nullptr;

        while (p){
            if (p->left){
                q = p->left;
                while (q->right) q = q->right;
                q->right = p->right;
                p->right = p->left;
                p->left = nullptr;
            }
            p = p->right;
        }
    }
};

算法2

(前序遍历模拟) $O(n)$

可以观察到，最后这条单链，就是前序遍历的顺序，所以我们前序遍历一遍，然后把树转成链即可。

时间复杂度

前序遍历时间复杂度$O(n)$。

参考文献

C++ 代码

class Solution {
private:
    TreeNode *pre = nullptr;
public:
    void flatten(TreeNode* root) {
        if (!root) return;

        if (pre){
            pre->right = root;
            pre->left = nullptr;
        }

        pre = root;
        TreeNode *left = root->left, *right = root->right;
        flatten(left);
        flatten(right);
    }
};

算法3

(逆向前序遍历模拟) $O(n)$

类似算法2，倒过来“右左根”这样便利实现可能更为方便、简洁。

时间复杂度

遍历每个节点时间复杂度$O(n)$。

参考文献

C++ 代码

class Solution {
private:
    TreeNode *pre = nullptr;
public:
    void flatten(TreeNode* root) {
        if (!root) return;

        flatten(root->right);
        flatten(root->left);

        root->right = pre;
        root->left = nullptr;
        pre = root;
    }
};