# 修改结构
## [Flatten Binary Tree to Linked List](https://leetcode.com/problems/flatten-binary-tree-to-linked-list/)
很符合递归思想的写法，美中不足是每次都要把左子树遍历一遍好去找尾端节点，如果整个树左子树体积非常大而右子树很小的话，时间复杂度会很高。最差的情况是，整个树是一个只有左边的链表，时间复杂度可以达到 O(n^2)，而且用递归还要花费栈空间。
```java
public class Solution {
public void flatten(TreeNode root) {
if(root == null) return;
flatten(root.left);
flatten(root.right);
TreeNode left = root.left;
TreeNode right = root.right;
root.left = null;
root.right = left;
while(root.right != null){
root = root.right;
}
root.right = right;
}
}
```
于是这题有特别赞的O(n)时间O(1)空间写法，还是利用 Morris 遍历。
Morris 遍历的特点是寻找左子树中能沿着右边走最长的节点，并且利用这个节点做文章；这题是把 right 指针直接指向 root 的右节点了，相当于每次缩进去【root.left -> 左子树最长向右路径】这段到右子树上，如此反复。因此省去了最坏情况下重复遍历寻找链表尾的过程。
```java
public class Solution {
public void flatten(TreeNode root) {
TreeNode cur = root;
while(cur != null){
if(cur.left == null){
cur = cur.right;
} else {
TreeNode prev = cur.left;
while(prev.right != null){
prev = prev.right;
}
prev.right = cur.right;
cur.right = cur.left;
cur.left = null;
}
}
}
}
```
## [Reverse LinkedList](https://leetcode.com/problems/reverse-linked-list/)
链表经典水题，把它放在这是因为它和下一题真的很像，只是维度上更单一而已。
```java
public class Solution {
public ListNode reverseList(ListNode head) {
ListNode prev = null;
while(head != null){
ListNode temp = head.next;
head.next = prev;
prev = head;
head = temp;
}
return prev;
}
}
```
## [Binary Tree Upside Down](https://leetcode.com/problems/binary-tree-upside-down/)
这题与其说是 Tree 类题目，不如说更像 LinkedList... 因为有很多的存 temp 和改动 reference ptr 的过程，尤其是迭代版，活脱一个反转列表。
* 迭代版
```java
public TreeNode upsideDownBinaryTree(TreeNode root) {
TreeNode curr = root;
TreeNode temp = null;
TreeNode prev = null;
while(curr != null) {
TreeNode next = curr.left;
curr.left = temp;
temp = curr.right;
curr.right = prev;
prev = curr;
curr = next;
}
return prev;
}
```
* 递归版
```java
public TreeNode upsideDownBinaryTree(TreeNode root) {
if(root == null || root.left == null) {
return root;
}
TreeNode newRoot = upsideDownBinaryTree(root.left);
root.left.left = root.right; // node 2 left children
root.left.right = root; // node 2 right children
root.left = null;
root.right = null;
return newRoot;
}
```
## [(FB) BST to doubly linked-list](http://www.1point3acres.com/bbs/forum.php?mod=viewthread\&tid=175727\&highlight=facebook)
LC 论坛的讨论帖
### 递归
### 思路 ：
* **完全就是 in - order 的递归结构，左-中-右**
* **核心在于 “中” 这步上，如何正确做好 “拼接” 工作**
* **我们需要存一个全局变量 prev 用于保存 "左子树的最后一个节点"，在每步上，和 root 做双向拼接； prev 初始化为 null;**
* **额外用于遍历 LinkedList 还需要存下 head ; 在 prev 为 null 的时候 root 就代表着最左面的节点，设一下就好，之后就不用管了。**
### 时间复杂度 O(n).
```java
private static class TreeNode{
int val;
TreeNode left,right;
public TreeNode(int val){
this.val = val;
}
}
static TreeNode prev;
static TreeNode head;
// In-order
public static void convert(TreeNode root){
if(root == null) return;
convert(root.left);
if(prev == null){
head = root;
} else {
root.left = prev;
prev.right = root;
}
prev = root;
convert(root.right);
}
public static void main(String[] args){
TreeNode node1 = new TreeNode(1);
TreeNode node2 = new TreeNode(2);
TreeNode node3 = new TreeNode(3);
TreeNode node4 = new TreeNode(4);
TreeNode node5 = new TreeNode(5);
TreeNode node6 = new TreeNode(6);
TreeNode node7 = new TreeNode(7);
TreeNode node8 = new TreeNode(8);
TreeNode node9 = new TreeNode(9);
TreeNode node10 = new TreeNode(10);
node2.left = node1;
node2.right = node3;
node4.left = node2;
node4.right = node5;
node6.left = node4;
node6.right = node9;
node9.left = node8;
node8.left = node7;
node9.right = node10;
convert(node6);
while(head != null){
System.out.print(" " + head.val);
head = head.right;
}
}
```
### 迭代(Stack)
* **In-order 跑一遍，每次 pop 出来的时候，我们就有 root 了；**
* **然后拼接的逻辑处理和递归的方法完全一样，这次连全局变量都不用，简单直接\~**
### 时间O(n)，空间 O(log n)
```java
// In-order
public static TreeNode convert(TreeNode root){
if(root == null) return null;
TreeNode prev = null;
TreeNode head = null;
Stack stack = new Stack<>();
TreeNode cur = root;
while(!stack.isEmpty() || cur != null){
while(cur != null){
stack.push(cur);
cur = cur.left;
}
TreeNode node = stack.pop();
if(prev == null){
head = node;
} else {
prev.right = node;
node.left = prev;
}
prev = node;
cur = node.right;
}
return head;
}
public static void main(String[] args){
TreeNode node1 = new TreeNode(1);
TreeNode node2 = new TreeNode(2);
TreeNode node3 = new TreeNode(3);
TreeNode node4 = new TreeNode(4);
TreeNode node5 = new TreeNode(5);
TreeNode node6 = new TreeNode(6);
TreeNode node7 = new TreeNode(7);
TreeNode node8 = new TreeNode(8);
TreeNode node9 = new TreeNode(9);
TreeNode node10 = new TreeNode(10);
node2.left = node1;
node2.right = node3;
node4.left = node2;
node4.right = node5;
node6.left = node4;
node6.right = node9;
node9.left = node8;
node8.left = node7;
node9.right = node10;
TreeNode head = convert(node6);
while(head != null){
System.out.print(" " + head.val);
head = head.right;
}
}
```
---
# 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://mnunknown.gitbook.io/algorithm-notes/binary_tree/63-_tree.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.