> For the complete documentation index, see [llms.txt](https://junnie.gitbook.io/nine-chapter/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://junnie.gitbook.io/nine-chapter/2.binary-tree/114.-flatten-binary-tree-to-linked-list-m.md).
# 114. Flatten Binary Tree to Linked List(M)
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**](https://en.wikipedia.org/wiki/Tree_traversal#Pre-order,_NLR) of the binary tree.
**Example 1:**
```
Input: root = [1,2,5,3,4,null,6]
Output: [1,null,2,null,3,null,4,null,5,null,6]
```
**Example 2:**
```
Input: root = []
Output: []
```
**Example 3:**
```
Input: root = [0]
Output: [0]
```
**Constraints:**
* The number of nodes in the tree is in the range `[0, 2000]`.
* `-100 <= Node.val <= 100`
**Follow up:** Can you flatten the tree in-place (with `O(1)` extra space)?
### Solution 1:
我们尝试给出这个函数的定义：
**给 `flatten` 函数输入一个节点 `root`，那么以 `root` 为根的二叉树就会被拉平为一条链表**。
我们再梳理一下，如何按题目要求把一棵树拉平成一条链表？很简单，以下流程：
1、将 `root` 的左子树和右子树拉平。
2、将 `root` 的右子树接到左子树下方，然后将整个左子树作为右子树。
[](https://labuladong.github.io/algo/images/%e4%ba%8c%e5%8f%89%e6%a0%91%e7%b3%bb%e5%88%97/2.jpeg)
上面三步看起来最难的应该是第一步对吧，如何把 `root` 的左右子树拉平？其实很简单，按照 `flatten` 函数的定义，对 `root` 的左右子树递归调用 `flatten` 函数即可：
```java
// 定义：将以 root 为根的树拉平为链表
void flatten(TreeNode root) {
// base case
if (root == null) return;
flatten(root.left);
flatten(root.right);
/**** 后序遍历位置 ****/
// 1、左右子树已经被拉平成一条链表
TreeNode left = root.left;
TreeNode right = root.right;
// 2、将左子树作为右子树
root.left = null;
root.right = left;
// 3、将原先的右子树接到当前右子树的末端
TreeNode p = root;
while (p.right != null) {
p = p.right;
}
p.right = right;
}
```
```
// 3、将原先的右子树接到当前右子树的末端
TreeNode p = root;
while (p.right != null) {
p = p.right;
}
```
**这段就是让原右子树接到原左子树的末尾**
[](https://camo.githubusercontent.com/6927c507572d675aeb861a146b8bc1d1cca18166d38f237b819052e595530298/68747470733a2f2f6c6162756c61646f6e672e67697465652e696f2f616c676f2f696d616765732f2565342562612538632565352538662538392565362561302539312565372562332562622565352538382539372f322e6a706567)
* 具体到这张图的话, 也就是让`5`接到`4`后面
* 如果**不用**`while`循环, 则`5`会直接接到`2`的后面, 这样点话`3`和`4`就丢失
你看，这就是递归的魅力，你说 `flatten` 函数是怎么把左右子树拉平的？说不清楚，但是只要知道 `flatten` 的定义如此，相信这个定义，让 `root` 做它该做的事情，然后 `flatten` 函数就会按照定义工作。另外注意递归框架是后序遍历，因为我们要先拉平左右子树才能进行后续操作。
### Solution 2: (Non-recursive pre-order traversal)
```
{
Stack stack = new Stack<>();
stack.push(root);
while (!stack.empty()) {
TreeNode node = stack.pop();
if (node.right != null) {
stack.push(node.right);
}
if (node.left != null) {
stack.push(node.left);
}
// connect
node.left = null;
if (stack.empty()) {
node.right = null;
} else {
node.right = stack.peek();
}
}
```
### Other Solution:
---
# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.
## 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://junnie.gitbook.io/nine-chapter/2.binary-tree/114.-flatten-binary-tree-to-linked-list-m.md?ask=
```
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.