No. 114 - Flatten Binary Tree to Linked List

---

LeetCode 114 – Flatten Binary Tree to Linked List

題目描述

Given the root of a binary tree, flatten the tree into a "linked list":

• The "linked list" should use the same TreeNode class where the right child pointer points to the next node in the list and the left child pointer is always null.
• The "linked list" should be in the same order as a pre-order traversal of the binary tree.

Example.

Input: root = [1,2,5,3,4,null,6]
Output: [1,null,2,null,3,null,4,null,5,null,6]

---

本題的目的是要將 binary tree 轉成 linked list，而 linked list 的順序是要照 preorder traversal 走訪的順序。

我們將講解兩種做法，分別是 postorder traversal 跟 morris traversal。

解法 1. Postorder Traversal

我們先以下面這個簡單的例子來說明

可以看到我們要轉成 linked list 其實就是把 left child 移到 right child 並將原本的 right child 接到後面。

我們在示範稍微複雜的 binary tree，可以看到當走訪到 2 的時候它就是把左邊 4 跟右邊 5 合併，然後再回到 1 把左子樹跟右子樹合併。

我們可以看到上面的流程它是先把 2 的左子樹右子樹合併才回到 1 去合併，但其實回去把 1 的左子樹跟右子樹合併前除了先把其左子樹合併，也要先確認右子樹延伸下去的左子樹跟右子樹也合併了。

而要確認這件事，我們可以用 postorder traversal 來做到，也就是先把左子樹跟右子樹都走訪了(合併)再回到父 node 來將其左子樹跟右子樹合併。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
  void postorderTraversal(TreeNode *node) {
    if (!node)
      return;
    postorderTraversal(node->left);
    postorderTraversal(node->right);
    // Merge left subtree with right subtree.
    TreeNode *tmp = node->right;
    node->right = node->left;
    node->left = nullptr;
    while (node->right)
      node = node->right;
    node->right = tmp;
  }
  void flatten(TreeNode* root) {
    postorderTraversal(root);
  }
};

解法 2. Morris Traversal

這個演算法有三個步驟:

• Step 1. 若當前 node 存在左子樹則走訪當前 node 的左子樹，把左子樹會走訪的最後一個 node 的 right pointer 指回這棵左子樹的 parent 的 right child，並接續 step 2。若不存在左子樹，則直接跳到 step 3。
• Step 2. 把左子樹改成接到右子樹。
• Step 3. 走訪 right child，並回到 step 1 重複動作。

以下面的例子為例，step 1 先走訪 node 1 的左子樹，並把左子樹會走訪的最後一個 node 5 的 right pointer 指向 node 1 的 right child node 3。step 2 把左子樹的 root，node 2 改接到 node 1 的 right child。接著 step 3 走訪 right child，node 2，然後繼續重複前面的步驟。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
  void flatten(TreeNode* root) {
    TreeNode *cur = root;
    while (cur) {
      TreeNode *prev = cur->left;
      if (prev) {
        while (prev->right)
          prev = prev->right;
        prev->right = cur->right;
        cur->right = cur->left;
        cur->left = nullptr;
      }
      cur = cur->right;
    }
  }
};

複雜度分析

在時間複雜度上，兩個方法的複雜度都是

$O(N)$。

空間複雜度上，postorder traversal 的複雜度為

$O(H)$。而 morris traversal 的複雜度為

$O(1)$。