# 114. Flatten Binary Tree to Linked List

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

## Thoughts

按照pre-order顺序依次把所有结点压成linked list，right作为next指针。pre-order遍历并把root->left和right存下来做为下次遍历的起点，global cur记录上次遍历到的点，在它后面插入当前结点并更新cur。

## Code

```cpp
/*
 * @lc app=leetcode id=114 lang=cpp
 *
 * [114] Flatten Binary Tree to Linked List
 */

// @lc code=start
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    void flatten(TreeNode* root) {
       stack<TreeNode*> s;
       s.push(root);
       TreeNode *last = nullptr;
       while (!s.empty()) {
           auto t = s.top(); s.pop();
           if (t == nullptr) continue;
           s.push(t->right);
           s.push(t->left);
           if (last != nullptr) {
               last->left = nullptr;
               last->right = t;
           }
           last = t;
       } 
    }
};
// @lc code=end


```

```cpp
/*
 * @lc app=leetcode id=114 lang=cpp
 *
 * [114] Flatten Binary Tree to Linked List
 */

// @lc code=start
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode *cur;
    void flatten(TreeNode* root) {
        if (root == nullptr) return;
        const auto left = root->left, right = root->right;
        root->left = nullptr;
        if (cur != nullptr) cur->right = root;
        cur = root;
        flatten(left);
        flatten(right);
    }
};
// @lc code=end


```

## Analysis

Errors:

1. TreeNode iter = node; 初始化错误。不是当前结点的最右，而是左子树的最右。

时间复杂度O(n)

## Ver.2

做一次pre-order traversal并把当前节点的左节点清空, 右节点连上pre-order的下一个(stack.peek()).

```
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public void flatten(TreeNode root) {
        if (root == null) {
            return;
        }

        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            if (node.right != null) {
                stack.push(node.right);
            }
            if (node.left != null) {
                stack.push(node.left);
            }
            if (!stack.isEmpty()) {
                node.right = stack.peek();
            }
                node.left = null;
        }
    }
}
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://hao-fu-1.gitbook.io/oj/binary_tree_and_divide_conquer/divide-and-concquer/flatten-binary-tree-to-linked-list.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.