> For the complete documentation index, see [llms.txt](https://mnunknown.gitbook.io/algorithm-notes/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://mnunknown.gitbook.io/algorithm-notes/binary_tree/63-_tree.md).

# 修改结构

## [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 论坛的讨论帖 <http://articles.leetcode.com/convert-binary-search-tree-bst-to/>

### 递归

### 思路 ： <http://www.geeksforgeeks.org/convert-given-binary-tree-doubly-linked-list-set-3/>

* **完全就是  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<TreeNode> 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;
        }
    }
```