《剑指offer》 第36题 二叉搜索树与双向链表

题目描述
输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。

思路1：

中序遍历的结果就是有序的，因此第1个方法就是考虑将中序遍历的结果记录，然后使之成为双向链表。这里的数据结构可以选择数组或者链表。以数组为例，将中序每遍历一个节点时，就添加到数组中，遍历完后数组就是有序的，然后再遍历一次数组，每遍历数组中的一个元素，就用把这个元素和下一个元素连起来。

写法1：使用数组的递归写法

import java.util.ArrayList;
public class Solution {
    public TreeNode Convert(TreeNode pRootOfTree) {
        if (pRootOfTree==null)
            return null;
       ArrayList<TreeNode> list=new ArrayList<>();
       Convert(list,pRootOfTree);//遍历
       return Convert(list);//遍历结束后调用连成链表的方法
    }

    public void Convert(ArrayList<TreeNode>list,TreeNode root){
        if (root!=null){
            Convert(list,root.left);
            list.add(root);//在左边遍历结束后，即将进入右边的调用时，将当前节点记录
//对中序遍历进行操作一般都在中间
            Convert(list,root.right);
        }
    }

    public TreeNode Convert(ArrayList<TreeNode> list){
        TreeNode head=list.get(0);
        TreeNode cur=head;
        for (int i=1;i<list.size();++i){//list集合没有length方法
            TreeNode node=list.get(i);
            node.left=cur;
            cur.right=node;
            cur=node;
        }
        return head;
    }
}
//之前的list是根据值的大小将所有的节点连了起来，但是每个节点自己的left和right并没有记录
//因此需要重新连接。

写法2：使用数组的非递归写法

由于是深度搜索，所以需要使用栈。层次遍历是队列。而前中后序遍历都属于深度遍历。

import java.util.ArrayList;
import java.util.Stack;
public class Solution {
    public TreeNode Convert(TreeNode pRootOfTree) {
        if (pRootOfTree==null)
            return null;
       ArrayList<TreeNode> list = new ArrayList<>();
       Stack<TreeNode> stack = new Stack<>();

        while(pRootOfTree!=null || stack.size()!= 0){
           if(pRootOfTree!=null ){//先遍历左子树
               stack.push(pRootOfTree);
               pRootOfTree = pRootOfTree.left;
           }else{//然后在遍历右子树前，将节点添加到list中
               list.add(stack.peek());
               pRootOfTree = stack.pop().right;
           }        
        }
       return Convert(list);
    }

    public TreeNode Convert(ArrayList<TreeNode> list){
        TreeNode head=list.get(0);
        TreeNode cur=head;
        for (int i=1;i<list.size();++i){
            TreeNode node=list.get(i);
            node.left=cur;
            cur.right=node;
            cur=node;
        }
        return head;
    }
}

思路2：

优化：之前是将排序好的list再串起来，那么考虑能否在遍历的同时，就把线给连上，遍历结束之时，链表就连接完成。同时还能不用额外的空间。

写法1：使用递归

public class Solution {
    public TreeNode Convert(TreeNode pRootOfTree) {
        if(pRootOfTree==null)
            return pRootOfTree;
        TreeNode pre = null;//当前节点的上一个节点
        pre = convertHelper(pRootOfTree,pre);
        TreeNode head = pre;
        while(head.left != null) {
            head = head.left;
        }  
        return head;
    }
    //将以node为根结点的树转化为排序链表，链表头部与pre链接，并返回最后一个结点
    private TreeNode convertHelper(TreeNode node,TreeNode pre) {
        //处理左子树，获得最大结点
        if(node.left!=null)
            pre = convertHelper(node.left, pre);
        //链接最大结点和根结点
        node.left = pre;
        if(pre!=null)
            pre.right = node;
        //处理右子树
        pre = node;
        if(node.right!=null)
            pre = convertHelper(node.right, pre);
        return pre;
    }
}

写法2：非递归

这种写法就需要一个变量，保存上一个节点。这样才能在遍历某个节点时，连起来。在最左边的叶子节点被遍历时，进行连接操作。

import java.util.Stack;
public class Solution {
    public TreeNode Convert(TreeNode pRootOfTree) {
        if(pRootOfTree==null)
            return null;
        Stack<TreeNode> stack = new Stack<TreeNode>();
        TreeNode head = null;//head只是记录双向链表的首个节点
        TreeNode pre = null;// 用于保存中序遍历序列的上一节点

        while(pRootOfTree!=null||!stack.isEmpty()){
             if(pRootOfTree != null) {
                stack.push(pRootOfTree);
                pRootOfTree = pRootOfTree.left;
            } else {
                pRootOfTree = stack.pop();//此时左子树遍历完了，弹出栈顶元素
                if(pre == null){ //pre初始值是null
                    pre = pRootOfTree;//因此将弹出的第一个节点，也就是序列的最左边的树赋值
                    head = pRootOfTree;
                  }      
                else {//进入这个else时，说明至少是第2个节点，此时进行连接。
                    pre.right = pRootOfTree;
                    pRootOfTree.left = pre;
                    pre = pRootOfTree;
                }
                pRootOfTree = pRootOfTree.right;//遍历完左子树后，应该向右走了
            }
        }
        return head;
    }
}

总结：使用数组或者队列的方式，容易想到，思路2反而不容易想到，思路2的难点在于，找到合适的连接时机。
尤其是递归的时候。