LeetCode 114. Flatten Binary Tree to Linked List [Medium] [C++] 解題筆記

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

For example, given the following tree:

    1
   / \
  2   5
 / \   \
3   4   6

The flattened tree should look like:

1
 \
  2
   \
    3
     \
      4
       \
        5
         \
          6

想法:

    這題最簡單的方式就是直接 inorder traverse，然後把結果存在一個vector中再串起來。但因為題目要求要

in-place flatten，因此我們可以改用 右子點->左子點->父節點 的順序遍歷，這樣最先完成遍歷的右子點變會在 list

的最後方，只要依序將上一個走訪完成的節點當成當前走訪的節點的右子點即可照上述的順序將 binary tree flatten 成

linked-list。

完整程式碼:

class Solution {
public:
    TreeNode* preVisited = nullptr;
    void flatten(TreeNode* root) {
        if (root == nullptr) { return; }
        flatten(root->right);
        flatten(root->left);
        root->right = preVisited;
        root->left = nullptr;
        preVisited = root;
        return;
    }
};