《剑指offer第二版》面试题36：二叉树与双向链表（java）

题目描述

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

题目分析

1. 题目要求是排好序的双向链表，二叉搜索树的中序遍历就是从小到大遍历每个节点，因此可以考虑和中序遍历结合.
2. 二叉树由两个指向子节点的指针，双向链表也是类似的结构，两者结构是类似的，可以让二叉树的left指针作为链表指向前一个节点的指针，二叉树right指针作为链表指向后一个节点的指针。
3. 对于二叉搜索树的任何一个节点，它的前一个节点是其左子树转化成排序链表中的最后一个节点，它的后一个节点是其由子树转化成链表后的第一个节点。很明显可以通过递归来做。

代码

   public TreeNode convert(TreeNode root){
       if (root == null) {
           return null;
       }
       // lastListNode是双向链表的最后一个节点
       TreeNode lastListNode = rConvert(root, null);
       TreeNode headListNode = lastListNode;
       // 找到双向链表的头节点并返回
       while (headListNode != null && headListNode.left != null) {
           headListNode = headListNode.left;
       }
       return headListNode;
   }

   /**
    * @param curNode 二叉树当前节点
    * @param lastListNode 当前双向链表的最后一个节点
    * @return 双向链表的最后一个节点
    */
   TreeNode rConvert(TreeNode curNode, TreeNode lastListNode){
       if (curNode == null) {
           return null;
       }

       if (curNode.left != null) {
           lastListNode = rConvert(curNode.left, lastListNode);
       }
       curNode.left = lastListNode;
       if (lastListNode != null) {
           lastListNode.right = curNode;
       }
       lastListNode = curNode;
       if (curNode.right != null) {
           lastListNode = rConvert(curNode.right, lastListNode);
       }
       return lastListNode;
   }