修改结构

Flatten Binary Tree to Linked List

很符合递归思想的写法，美中不足是每次都要把左子树遍历一遍好去找尾端节点，如果整个树左子树体积非常大而右子树很小的话，时间复杂度会很高。最差的情况是，整个树是一个只有左边的链表，时间复杂度可以达到 O(n^2)，而且用递归还要花费栈空间。

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 -> 左子树最长向右路径】这段到右子树上，如此反复。因此省去了最坏情况下重复遍历寻找链表尾的过程。

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

链表经典水题，把它放在这是因为它和下一题真的很像，只是维度上更单一而已。

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

这题与其说是 Tree 类题目，不如说更像 LinkedList... 因为有很多的存 temp 和改动 reference ptr 的过程，尤其是迭代版，活脱一个反转列表。

• 迭代版

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;
}

• 递归版

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

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).

    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)

    // 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;
        }
    }