剑指Offer36：二叉搜索树和双向链表（Java)

题目描述：


解题思路：
    从题目我们可以发现，这个双向链表的顺序是中序遍历。而中序遍历的顺序是左节点、根节点、右节点。这个可以使用递归的方法去实现它。其次双向链表，我们可以通过定义两个指针head、last实现它。head表示头节点，last表示上一个节点。当遍历到第一个元素的时候，判断头节点是否为空，为空则把头节点指向第一个节点。然后判断last节点是否为空，last节点为空，则证明当前是遍历的是头节点，last节点等于头节点。如果last节点不为空，则证明当前遍历的是头节点后面的节点，此时可以建立两个节点的双向联系。最后，我们再把头尾节点连起来，返回head即可。

代码实现：

class Solution {
	//head当前结点、last前一个结点
    Node head,last;
    public Node treeToDoublyList(Node root) {
        if(root==null) return null;
        //中序遍历：左 -> 根 -> 右
        digui(root);
        //头尾结点相连
        last.right=head;
        head.left=last;
        return head;
    }

    void digui(Node root){
    	//跳出循环
        if(root==null)  return ;
        digui(root.left);
        //设立头节点
        if(head==null)  head=root;
        //如果last节点不为空
        if(last!=null){
            last.right=root;
            root.left=last;
            last=root;
        } 
        //如果last节点为空
        if(last==null)  last=head;
        digui(root.right);
    }
}

执行结果：