Tree to Doubly Linked List

Tree to Doubly Linked List

convert a binary tree to a circular doubly-linked list. (I add these words: use right pointer as next pointer, use left pointer as previous pointer.)


Naive Thinking: 这道题目有点宽泛啊，没说具体怎么映射。但是有一点很合我意的就是，它把指针的概念变成一个广义的，left node和right node就一定要做左右子节点的指针吗，就不能做双向链表的前后指针吗，这一点参见我在Populating Next Right Pointers in Each Node II中最后那个引用的例子。所以我自己加的将right变成next，left变成pre，看了别人的回答也是差不多这样的。嗯，这道题很好。

那么我的基本思路就是利用原树节点的左右子节点指针做前后指针。但是具体怎么映射必须得有章法吧，将树写成线性形式的方法有三种:前序遍历，中序遍历，后序遍历。

那么这道题是考验二叉树的遍历咯？肯定在考，即使不是只考这个。这时赶快在心里默默写下三种遍历。一个直觉就是将树转换成链表，一个recursive的算法，肯定不是三种遍历都可以，应该只有一种遍历可以，这道题应该有在看是否能用出正确的遍历方式。仔细分析

基本框架大概是这样的
void traversal(TreeNode root){
    if(root==null){return;}
    if(root.left!=null){traversal(root.left);}
    if(root.right!=null){traversal(root.right);}
} 

问题一，traversal只有一个参数，无返回值，能否确保在回溯过程中树不断掉。比如一旦连了next(right)，right node 可能就找不回来了。

问题二，同时要连next 和 pre，也就是说同时要可能改变right 和left 节点的链接方式，如何做到连好之后还能找回right node 和left node。

回答一，感觉上一个参数应该足够，无返回值有点不好弄，因为如果把一棵树变成链表，一个对树的recursive函数把链表连成圈的，好难，简直无法想象。感觉先把root当成头，连好后面的得到一个尾巴，将一头一尾在外面手动链接才是一个可行的方案。传进去的值是root，如果能传出来的正好是尾巴就好了。那么想到这里，哪种遍历这个问题也迎刃而解了，root必须是第一个遍历的节点，只有中序遍历才能做到。

回答二，为何要同时连next和pre, 连好任意一个，另外一个不就也算连上了吗？

根据以上推导我写了下面这段代码。算法复杂度是O(n)，O(n) space  （其实是preorder)
后面有个用于测试代码可行与否的main函数。

// public class TreeNode{
//         int val;
//         TreeNode left;
//         TreeNode right;
//         TreeNode(int x){
//             val = x;
//             left = null;
//             right = null;
//         }
//     }

public class Solution{

    public void tree2DoublyList(TreeNode root){
        TreeNode end = traversal(root);
        TreeNode cur = root;
        if(cur==null){return;}
        root.left = end;
        while(cur.right!=null){
            TreeNode tail = cur.right;
            tail.left = cur;
            cur = tail;
        }
        cur.right = root;
        return;
    }

    private TreeNode traversal(TreeNode root){
        if(root==null){return null;}
        TreeNode temp = root.right;
        TreeNode fromLeft = null, fromRight = null;
        root.right = root.left;
        fromLeft = root.left!=null?traversal(root.left):root;
        fromLeft.right = temp;
        fromRight = temp!=null?traversal(temp):fromLeft;
        return fromRight;
    }
    
   // test correctness
    public static void main(String args[]){
        Solution s = new Solution();
        List<TreeNode> list = new ArrayList<TreeNode>();
        for(int i = 0; i < 10;i++){
            TreeNode node = new TreeNode(i);
            list.add(node);
        }
        for(int i = 0;i < list.size();i++){
            if(2*i+1 < list.size())
                list.get(i).left = list.get(2*i+1);
            if(2*i+2 < list.size())
                list.get(i).right = list.get(2*i+2);
        }
        s.showTree(list.get(0));
        s.tree2DoublyList(list.get(0));
        TreeNode cur = list.get(0);
        for(int i = 0;i < list.size();i++){
            System.out.print(cur.val + "  ");
            cur = cur.right;
        }
        System.out.println();
        for(int i = 0;i < list.size();i++){
            System.out.print(cur.val + "  ");
            cur = cur.left;
        }
        System.out.println();
    }

    private void showTree(TreeNode root){
        if(root==null){return;}
        System.out.println(root.val);
        if(root.left!=null)
            showTree(root.left);
        if(root.right!=null)
            showTree(root.right);
    }

}


Improved Way: 这道题我被面到了，但是条件不一样了，变成将二叉树转化成排好序的doubly-linked-list。

这里知道了一个规律，binary search tree一般就要跟inorder traversal 联系起来了。 我上面的代码相当于是一个preorder 顺序的doubly-linked-list。我下面的代码是对应inorder traversal recursive的方法。

这是我在面试时候写的，算法复杂度是O(n)，space O(n)。将recursive函数改为返回一头一尾两个节点了，质量不高的代码。

public void tree2DoublyList_inorder(TreeNode root){
        List<TreeNode> list = inorder(root);
        TreeNode head = list.get(0);
        TreeNode tail = list.get(1);
        TreeNode pre = head;
        while(pre!=tail){
            TreeNode cur = pre.right;
            cur.left = pre;
            pre = cur;
        }
        head.left= tail;
        tail.right = head;
        return;
    }

    private List<TreeNode> inorder(TreeNode root){
        List<TreeNode> list = new ArrayList<TreeNode>();
        if(root==null){return list;}
        TreeNode head1, head2, tail1, tail2;
        List<TreeNode> fromLeft = inorder(root.left);
        if(fromLeft.size()!=0){
            head1 = fromLeft.get(0);
            tail1 = fromLeft.get(1);
            tail1.right = root;
        }else{
            head1 = root;
            tail1 = root;
        }
        List<TreeNode> fromRight = inorder(root.right);
        if(fromRight.size()!=0){
            head2 = fromRight.get(0);
            tail2 = fromRight.get(1);
            root.right = head2;
        }else{
            head2 = root;
            tail2 = root;
        }
        list.add(head1);
        list.add(tail2);
        return list;
    }


比较好的方法应该是这样的。用一个list<TreeNode>存，任意顺序遍历tree，每次遍历到哪个节点就add哪个节点，这个方法估计才是面试官想要的算法。

这样子做的好处一是清晰简洁，二是如果想要变换顺序(inorder，preorder，postorder)，只需要改变recursive函数中遍历的顺序即可，算法复杂度是O(n)， space也是O(n)。

public void tree2DoublyList(TreeNode root){
        List<TreeNode> list = new ArrayList<TreeNode>();
        traversal(root, list);
        for(int i = 0;i < list.size()-1;i++)
            list.get(i).right = list.get(i+1);
        list.get(list.size()-1).right = list.get(0);
        for(int i = 1;i < list.size();i++)
            list.get(i).left = list.get(i-1);
        list.get(0).left = list.get(list.size()-1);
        return;
    }

    private void traversal(TreeNode root, List<TreeNode> list){
        if(root==null){return;}
        // adjust the order to achieve inorder, preorder, postorder
        traversal(root.left,list);
        list.add(root);
        traversal(root.right,list);
        return;
    }