Description

难度中等：剑指 Offer 36. 二叉搜索树与双向链表
输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的循环双向链表。要求不能创建任何新的节点，只能调整树中节点指针的指向。
以下面的二叉搜索树为例：

剑指Offer 36. 二叉搜索树与双向链表 - 图1
我们希望将这个二叉搜索树转化为双向循环链表。链表中的每个节点都有一个前驱和后继指针。对于双向循环链表，第一个节点的前驱是最后一个节点，最后一个节点的后继是第一个节点。
下图展示了上面的二叉搜索树转化成的链表。“head” 表示指向链表中有最小元素的节点。
剑指Offer 36. 二叉搜索树与双向链表 - 图2

特别地，我们希望可以就地完成转换操作。当转化完成以后，树中节点的左指针需要指向前驱，树中节点的右指针需要指向后继。还需要返回链表中的第一个节点的指针。

Solution

由于二叉搜索树是有序的，链接的后的双向链表也要求是有序的，而在遍历二叉树的算法中，中序遍历是按顺序进行遍历的，所以可以利用中序遍历的思想来解决这个问题。
非递归的中序遍历
使用一个栈来保存遍历的节点，同时使用双指针 fast、slow，fast 指针进行中序遍历，而 slow 则指向 fast 的前一个节点，依次将 fast 与 slow 链接在一起

  1. /*
  2. // Definition for a Node.
  3. class Node {
  4.     public int val;
  5.     public Node left;
  6.     public Node right;
  7.     public Node() {}
  8.     public Node(int _val) {
  9.         val = _val;
  10.     }
  11.     public Node(int _val,Node _left,Node _right) {
  12.         val = _val;
  13.         left = _left;
  14.         right = _right;
  15.     }
  16. };
  17. */
  18. class Solution {
  19.     public Node treeToDoublyList(Node root) {
  20.         if (root == null) return root;
  21.         Stack<Node> stack = new Stack<>();
  22.         Node fast = root, slow = null,res = null;
  23.         // 中序遍历
  24.         // 选取二叉树中最小元素的节点，也就是双向链表中的头节点
  25.         while (fast != null){
  26.             stack.push(fast);
  27.             fast = fast.left;
  28.         }
  29.         res = stack.peek();
  30.         while (!stack.isEmpty() || fast != null){
  31.             if (fast != null){
  32.                 stack.push(fast);
  33.                 fast = fast.left;
  34.             }else {
  35.                 fast = stack.pop();  
  36.                 if (slow != null){    // 将 fast 与 slow 节点进行链接
  37.                     fast.left = slow;
  38.                     slow.right = fast;
  39.                 }
  40.                 slow = fast;   // 更新 slow 节点的指向
  41.                 fast = fast.right;  // 更新 fast 节点的指向
  42.             }
  43.         }
  44.         res.left = slow;
  45.         slow.right = res;
  46.         return res;
  47.     }
  48. }

递归版本的中序遍历

  1. class Solution {
  2.     Node pre = null;
  3.     Node res = null;
  4.     public Node treeToDoublyList(Node root) {
  5.         if (root == null) return root;  // 处理边界条件
  6.         // 中序遍历，链接节点
  7.         inOrder(root);
  8.         // 构建成循环双向链表
  9.         res.left = pre;
  10.         pre.right = res;
  11.         return res;
  12.     }
  13.     public void inOrder(Node cur){
  14.         if ( cur == null)  // 边界条件
  15.             return ;
  16.         inOrder(cur.left);      // 递归左子树
  17.         if (pre == null)    res = cur;   // pre 为空，当前节点为链表的 head 节点
  18.         else    pre.right = cur;    // pre 不为空，链接 pre 和 cur 节点
  19.         cur.left = pre;
  20.         pre = node;
  21.         inOrder(node.right);  // 递归右子树
  22.     }
  23. }

执行结果：通过
执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
内存消耗：38.1 MB, 在所有 Java 提交中击败了95.79%的用户